# Push down automaton for Language of same number of as and bs

Find a pushdown automaton $M$, so that $L(M)=\{w \in \{a,b\}^*\ |\ |w|_a=|w|_b\}$, where $|w|_a$ denotes the number of $a$s in a word $w$.

My solution

I'm using the Wikipedia notation. $$M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, \{q_0\})$$ $$Q=\{q_0\}, \Sigma = \{a,b\}, \Gamma = \{Z_0, A,B\}$$ $$\delta\text{ has the following instructions:}$$ $$(q_0, \varepsilon, Z_0, q_0, \varepsilon),$$ $$(q_0, a, Z_0, q_0, AZ_0),$$ $$(q_0, b, Z_0, q_0, BZ_0),$$ $$(q_0, a, A, q_0, AA),$$ $$(q_0, b, A, q_0, \varepsilon),$$ $$(q_0, b, B, q_0, BB)\text{ and}$$ $$(q_0, a, B, q_0, \varepsilon).$$

Questions

1. Is this correct? Can it be simplified?
2. If so, how can I argue (not neccessarily proof) its correctness?
• To argue why it's correct, write down what you thought when you constructed the PDA. – adrianN Jan 19 '17 at 16:09
• copy-paste error in your last instruction: it duplicates an earlier one. – Hendrik Jan Jan 19 '17 at 21:14

As adrianN and Yuval say, correctness is shown by explaining your ideas, in particular what the automaton stores in its states and stack.

Just as a fun fact: you have constructed a single state PDA, which essentially means you have constructed a context-free grammar. The construction is reverse from the one given in a remark in Wikipedia (concerning CFG in Greibach normal form).

In this case your productions are equivalent to

$Z\to \varepsilon$, $Z\to aAZ$, $Z\to bBZ$, $A\to aAA$, $A\to b$, $B\to bBB$, $B\to a$.

You can shave off one production and use less nonterminals by starting with the grammar $S\to SS$, $S\to aSb$, $S\to bSa$, $S\to\varepsilon$, which is a variant of the well-formed parenthesis grammar in wikipedia. This is not yet a PDA,to this you need a more Greibach-like format:

$S\to SS$, $S\to aSB$, $S\to bSA$, $S\to\varepsilon$, $A\to a$, $B\to b$.

More efficient perhaps, but the stacks of your original PDA have a clear meaning, helping its correctness proof.

• Thanks! This looks just like a grammar I learned about earlier, so I can make use of that. – Seims Jan 19 '17 at 22:25

The usual approach is to prove by induction the following kind of statement:

The set of configurations reachable from the initial state upon reading a word $w$ is ...

Here ... depends on $w$. Having proved this kind of statement, you can deduce which words are accepted by your machine, hence proving its correctness.