Reference no: EM133270338

Question 1: For each of the following languages, construct a context-free grammar generating the language; briefly and precisely describe the strings generated by each variable in the grammar. Notes: You should aim to give the simplest grammars possible, and offer brief explanations about how your grammars work.
(a) {aⁱbⁱ ≥ 1, and |i - j| i ≤ 3}.
(b) {aⁱb^2jc^jd^k |i, j,k ≥ 1, and 2i ≤ k}.
(c) {aⁱb^j | i,j ≥ 0, and i ≠ j}.
(d) {x₁x₂cy | x₁, x₂, y ∈ {a, b}*, and there exists x ∈ {a, b}* with x₁xx₂ = Y^r }.
(e) {aⁱb^jc^k | i > j > k ≥ 0. Ignore this part: incorrect membership condition.

Question 2: Read: (1) our textbook [Sip12] Example 2.3 for the context-free grammar G, and (2) lecture notes that a precise specification of the following language L,

L = {x ∈ {a, b}* | for every prefex u of x, #_a(u) ≥ #_b(u), and #_a (x) - #_b(x)}.

Following the framework shown in lectures that proves the correctness of a context-free grammar, give a detailed proof of correctness of L(G) = L

Question 3: Consider the following language:

L = {w ∈ {a, b}* | 2#_a(w) ≠ 3#_b(w)},

where #_c,(w) denotes the number of symbol c occurring in the string w.

Construct a pushdown automaton accepting the language L (no conversion from context-free grammar to pushdown automaton is accepted); give brief and precise interpretation of the states and transitions of your machine.

Question 4: Let G be a context-free grammar in Chomsky Normal Form with it variables. Prove that, if G derives some string with a derivation having at least 272 steps, L(G) is infinite.

Question 5. Let ∑ be an alphabet. The symmetric difference of two languages A, B ⊆ ∑*, denoted by AΔB, is defined as:

(A ∩ B‾) U (A‾ ∩ B).

Prove that if A ⊆ ∑* is a context-free language and B ⊆ ∑* is a finite language, then the language AΔB is context-free.