Example 5.2.4. In this example we seek a context-free grammar for all (and only) the strings over _ = {a,b} with an equal number of 'a's and 'b's. Such a grammar is not so easy to formulate directly. So instead we develop a PDA, and then transform it into the desired grammar.
Only a single is required and so it need not be shown.
while {(_,Z), (a,B), (b,A)} push _; /* accept (empty stack) if excess=0; or, reduce excess upon mismatch */
while {(a,Z)} push AZ; /* excess 'a' is 1 */
while {(a,A)} push AA; /* increment excess 'a' */
while {(b,Z)} push BZ; /* excess 'b' is 1 */
while {(b,B)} push BB /* increment excess 'b' */
| Previous slide | Next slide | Back to first slide | View graphic version |