Problem Construct the CFL accepting the language described by the PDA

[figure: q_{0}; q_{1}; q_{2}; ϵ, ϵ → $; 0, ϵ → A; 1, A → ϵ; ϵ, $ → ϵ]

over the input alphabet Σ = {0, 1} and stack alphabet Γ = {A, $}, according to the construction given in class and in Lemma 2.15 of Sipser. Finally, prune the rules in the resulting CFL to produce a CFL for the same language, but with a small number of rules (Hint: You should end up with four rules).

Answer Step 1:

\begin{aligned}\begin{aligned}(q_{1}, $) & ∈ & δ(q_{0}, ϵ, ϵ) \\ (q_{2}, ϵ) & ∈ & δ(q_{1}, ϵ, $) \end{aligned} & ⇒ & A_{02} → A_{11} \\ \begin{aligned}(q_{1}, A) & ∈ & δ(q_{1}, 0, ϵ) \\ (q_{1}, ϵ) & ∈ & δ(q_{1}, 1, A) \end{aligned} & ⇒ & A_{11} → 0A_{11}1 \end{aligned}

Step 2:

\begin{aligned}A_{00} & → & A_{00}A_{00} | A_{01}A_{10} | A_{02}A_{20} \\ A_{11} & → & A_{10}A_{01} | A_{11}A_{11} | A_{12}A_{21} \\ A_{22} & → & A_{20}A_{02} | A_{21}A_{12} | A_{22}A_{22} \\ A_{01} & → & A_{00}A_{01} | A_{01}A_{11} | A_{02}A_{21} \\ A_{10} & → & A_{10}A_{00} | A_{11}A_{10} | A_{12}A_{20} \\ A_{02} & → & A_{00}A_{02} | A_{01}A_{12} | A_{02}A_{22} \\ A_{20} & → & A_{20}A_{00} | A_{21}A_{10} | A_{22}A_{20} \\ A_{12} & → & A_{10}A_{02} | A_{11}A_{12} | A_{12}A_{22} \\ A_{21} & → & A_{20}A_{01} | A_{21}A_{11} | A_{22}A_{21} \end{aligned}

Step 3:

\begin{aligned}A_{00} & → & ϵ \\ A_{11} & → & ϵ \\ A_{22} & → & ϵ \end{aligned}

Now combine everything and prune:

\begin{aligned}A_{02} & → & A_{11} \\ A_{11} & → & 0A_{11}1 | A_{11}A_{11} | ϵ \end{aligned}

A_{02} is the start symbol.