Make a Pushdown Automaton to accept the language an bn n gr

Make a Pushdown Automaton to accept the language {a^n b^n | n greaterthanorequalto 0} generated by the context-free grammar S rightarrow aSb S rightarrow logicaland

Solution

Give a context-free grammar generating the language

L=the complement of the lannguage {a

n

b

n

|n_> 0}.

Idea:we can break this language onto the union of several simpler language: L={ai bj | i>j} u

{ai bj | i<j } u (a u b)*b(a u b)*a(a u b)*.

,That is, all string of a\'s followed by b\'s in which the number of a\'s and b\'s differ, unioned with all string not of the from ai bj.

Frist, we can achieve the union of the CFGS for the three languages:

S-> S1|s2|s3

Now, the set of string {ai bj | i>j } is generated by a simple CGF:

S1-> as1b|as1|a

1similarly for {ai bj | i< j }:s2 -> as2b |s2b |b

Finally, ( a u b)*b(a u b)*a( a u b)*

is easily generated as follows:

s3 -> XbXaX

x -> ax|bX|