The task

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).$$


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

| cite | improve this answer | |
  • $\begingroup$ Thanks! This looks just like a grammar I learned about earlier, so I can make use of that. $\endgroup$ – 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.