Let L be the language over alphabet $\{$a$,$ b$\}$ of strings with an equal number of as and bs $($ie$,1,$ ab$,$ ba$,$ aabb, abab, abba, etc$).$

Lis a context$-$free language and we can prove it by showing a PDA that accepts L$.$ We can use the PDA stack to keep track of how many more of one character we have consumed than the other $($so if the

PDA has consumed $3$ more as than bs there should be $3$ as on the stack$).$ Write a PDA that accepts L following this strategy. My solution has two states and seven triples.

However, L is not a regular language. In a proof that L is not regular we assume L is regular with pumping length p and then pick a string that would allow an easy contradiction using the pumping lemma.

What string would you choose?

The Pumping Lemma says that your string can be broken into xyz where y is a non$-$empty substring of the first p characters of your string and that both xz and xyyz are also in L$.$

But

$($write either xz or xyyz$)$ is not in L because: