The Gateway to Computer Science Excellence
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).
in Theory of Computation by Veteran (60.6k points) | 8 views

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,833 questions
57,713 answers
107,653 users