8 views

Let G be the following grammar:

• $S \rightarrow T\dashv$
• $T \rightarrow T aT b \mid T bT a | \epsilon$
1. Show that $L(G) = \{w\dashv \: \mid w\: \text{contains equal numbers of a’s and b’s} \}$. Use a proof by induction on the length of $w$.
2. Use the DK-test to show that G is a DCFG.
3. Describe a DPDA that recognizes L(G).
| 8 views