Problem 1: Find context-free grammars generating the following languages, and justify that they generate them:
(a) L1 = {aibjck | i = j or j = k}.
(b) L2 = {aibjck | i ≠ j + k }
Problem 2: Prove that the CFG G with productions S → 0S1S | 1S0S | Λ generates the language L = {x ∈ {0, 1}∗ | n0(x) = n1(x)}.
Problem 3: Show that if L is accepted by a PDA in which no move replaces the top stack symbol with Λ, then L is regular.
Problem 4: Suppose that M is a PDA accepting L. Describe how to construct a PDA accepting the language L∗ and justify that it does accept L∗. (Remember that the stack may become empty when M accepts a string!)
Problem 5: Show that if there is a PDA M = (Q, Σ, Γ, q0, Z0, A, δ) accepting language L by empty stack (i.e. x ∈ L if and only if (q0, x, Z0) €∗M (q, Λ, Λ) for some state q ∈ Q), then there is a PDA M1 = (Q1, Σ, Γ1, q1, Z1, A1, δ1) accepting L by final state (i.e. x ∈ L if and only if (q1, x, Z1) €∗M1 (q, Λ, α) for some α ∈ Γ∗1 and q ∈ A1).
Attachment:- TOC.rar