Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Comp335 Introduction to Theoretical Computer Science

Winter 2023

Assignment 3. Due date: March 22, by 23:59 P.M.

1.  Give context-free grammars for each of the following languages.

(a)  {ah bk am bn  : h + k = m + n}

(b)  {ai bj ak  : (i = j and k 2 0) or (i 2 0 and j > k)}

2. Prove that if G is the context-free grammar defined by the productions S → aSbS ∣ bSaS ∣e then L(G) = {w e {a, b}*  : na (w) = nb (w)}.

3. In each case below, show that the grammar is ambiguous, and find an equivalent unambiguous grammar.

(a)  S → SS ∣ ab ∣ a

(b)  S → ABA,  A → aA ∣ e,  B → bB ∣e

4. Design a PDA to accept each of the following languages. You may design your PDA to accept either by final state or empty stack, whichever is more convenient.

(a)  {ah bk am bn  : h + k = m + n}

(b)  {an b : n 2 0} u {abn  : n 2 0} u {an bn  : n 2 0}

5.  Give an example of a PDA P = (Q, Σ , Γ, δ, q0 , Z0 , F ) is a PDA, and strings x, y e Σ, α, β, γ e

(Σ u Γ)*  such that (q, x, αγ)上(*) (p, y, βγ) but (q, x, α)上(*) (p, y, β) does not hold.

6. Using the methods in the text,

(a) convert the grammar G = ({S, A}, {0, 1}, {S → 0S1∣A, A → 1A0∣S∣e}, S}) to a PDA that

accepts exactly L(G).

(b) convert the PDA P = ({q0 , q1 }, {a, b}, {A, Z0 }, δ, q0 , Z0 , {q1 }), where

δ(q0 , a, Z0 ) = {(q0 , AZ0 )},  δ(q0 , b, A) = {(q0 , AA)},  δ(q0 , a, A) = {(q1 , e)} to a CFG G, such that L(G) = L(P).

7.  Convert the following grammars into Chomsky Normal Form

(a)  S → ASB ∣ e,  A → aAS ∣ a,  B → SbS ∣ A ∣bb.

(b)  S → 0A0 ∣ 1B1 ∣ BB,  A → C,  B → S ∣ A, C → S ∣e.

8. Use the Pumping Lemma for CFL’s to show that the following languages are not Context-Free.

(a)  {w e {a, b, c}* : na (w) < nb (w) and na (w) < nc (w)}

(b)  {an bj ck dl  : n < k and j < l}