Given two languages A and B, let A/B denote the language {w | w x ∈...

Given two languages A and B, let A/B denote the language

{w | w x ∈ A for some x ∈ B}.

Show that if A is a context-free language and B is a regular language, then A/B is a context-free

language. hint (construct PDAs)

Solutions

Expert Solution

Here we are given two languages

A : Context Free Language

B: Regular Language

And A/B denotes the language as {w | w x ∈ A for some x ∈ B}

We need to prove that A/B is context free.

Let M be PDA for A and N be DFA for B.

Let's consider that we want to show that if a string wx is accepted by a CGF, then we know that x will by default be accepted by regular language and thus is also accepted by CFG.And now we will prove it by contradiction. Assuming that A is CFG , B is regular but A/B is not CFG.

First we will construct a PDA for A/B by modifying M so that it can run parallely for this we can use cartesian product. To build PDA for A/B we have 2 steps:

Step 1: read i/p word x and advance it in M and ignore state of N. This will be for word w of language.

Step 2: after reaching the end of w we can perform epsilon transitions in order to reach an accepting state of cartesian product i.e. M x N. The word x will be assumed to continue to advance in M and also start to advance in N and that has to reach acceptance in both M and N automata simultaneously. In simple words You can say that from this point the machine gusses a string x and processes x by both M and N.

The machine will accept only if both mahines simultaneously accepts it.

From the below diagram you can easily understand the realtion between different types of languages.

venereology answered 1 year ago

Next > < Previous

Related Solutions

Let R be a ring (not necessarily commutative), and let X denote the set of two-sided...

Let R be a ring (not necessarily commutative), and let X denote the set of two-sided ideals of R. (i) Show that X is a poset with respect to to set-theoretic inclusion, ⊂. (ii) Show that with respect to the operations I ∩ J and I + J (candidates for meet and join; remember that I+J consists of the set of sums, {i + j} where i ∈ I and j ∈ J) respectively, X is a lattice. (iii) Give...

Let W denote the set of English words. For u, v ∈ W, declare u ∼...

Let W denote the set of English words. For u, v ∈ W, declare u ∼ v provided that u, v have the same length and u, v have the same first letter and u, v have the same last letter. a) Prove that ∼ is an equivalence relation. b) List all elements of the equivalence class [a] c) List all elements of [ox] d) List all elements of [are] e) List all elements of [five]. Can you find more...

Two fair dice are rolled at once. Let x denote the difference in the number of...

Two fair dice are rolled at once. Let x denote the difference in the number of dots that appear on the top faces of the two dice. For example, if a 1 and a 5 are rolled, the difference is 5−1=4, so x=4. If two sixes are rolled, 6−6=0, so x=0. Construct the probability distribution for x. Arrange x in increasing order and write the probabilities P(x) as simplified fractions.

Suppose two fair dice are rolled. Let X denote the product of the values on the...

Suppose two fair dice are rolled. Let X denote the product of the values on the dice and Y denote minimum of the two dice. Find E[X] and E[Y] Find Var X and Var Y Let Z=XY. Find E[Z]. Find Cov(X,Y) and Corr(X,Y) Find E[X|Y=1] and E[Y|X=1]

For a given language L = { w | na(w) + nb(w) = nc(w) } where...

For a given language L = { w | na(w) + nb(w) = nc(w) } where S = G = {a, b, c} Looking for answer to 3 Construct a PDA M that accepts L with S = G = {a, b, c} Show the sequence of instantaneous descriptions for the acceptance of acacbcbc by M in 1). Give a CFG G that generates L, L(G) = L.

Let X = NN endowed with the product topology. For x ∈ X denote x by...

Let X = NN endowed with the product topology. For x ∈ X denote x by (x1, x2, x3, . . .). (a) Decide if the function given by d : X × X → R is a metric on X where, d(x, x) = 0 and if x is not equal to y then d(x, y) = 1/n where n is the least value for which xn is not equal to yn. Prove your answer. (b) Show that no...

You roll two fair dice, and denote the number they show by X and Y. Let...

You roll two fair dice, and denote the number they show by X and Y. Let U = min{X, Y } and V = max{X, Y }. Write down the joint probability mass function of (U, V ) and compute ρ(U, V ) i.e the correlation coefficient of U and V

Two dice are rolled. Let the random variable X denote the number that falls uppermost on...

Two dice are rolled. Let the random variable X denote the number that falls uppermost on the first die and let Y denote the number that falls uppermost on the second die. (a) Find the probability distributions of X and Y. x 1 2 3 4 5 6 P(X = x) y 1 2 3 4 5 6 P(Y = y) (b) Find the probability distribution of X + Y. x + y 2 3 4 5 6 7 P(X...

Let E(n) denote the expected return on asset i and B. denote the corresponding beta. In addition, let E(rm) denote the expected

Let E(n) denote the expected return on asset i and B. denote the corresponding beta. In addition, let E(rm) denote the expected return on the market portfolio and Bm denote the corresponding beta. Define and sketch the Security Market Line (SML). Hint: Use E(rm) - r = 8%, r = 3%, B. = 1.25 and B2 = 0.6.

Proposition 8.59. Suppose that X, Y, W, Z, A, B are sets. Let f : X...

Proposition 8.59. Suppose that X, Y, W, Z, A, B are sets. Let f : X → Y , W ⊆ X, Z ⊆ X, A ⊆ Y , and B ⊆ Y . Then the following are true: prove the following ? (1) f(W ∩ Z) ⊆ f(W) ∩ f(Z). (2) f(W ∪ Z) = f(W) ∪ f(Z). (3) f−1(A ∩ B) ⊆ f−1(A) ∪ f−1(B) 4) f−1(A ∪ B) = f−1(A) ∪ f−1(B). (5) X−f−1(A)⊆f−1(Y −A). (6) W...

Subjects