edited by
233 views
0 votes
0 votes

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).
edited by

Please log in or register to answer this question.

Related questions

1 votes
1 votes
0 answers
1
0 votes
0 votes
0 answers
3
0 votes
0 votes
0 answers
4