What is the PDA for this language with three 0's per one 1?

Question

I am trying to find a PDA for $L = \{0^{3i} 1^i \mid i \geq 0\}$ but I am struggling. I was trying to find a DFA and then convert it to PDA but now know that DFA's can't keep count. Any ideas?

Answer 1

Deterministic Finite Automata CAN'T count. You need an Automata with memory, like a 'Stack-Machine', to be able to parse such a grammar.

Answer 2

As has been mentioned before, you cannot find a DFA and convert it to a PDA, because the language is not regular. But you can start with a DFA as the skeleton of your PDA. Without counting, your language becomes $0^*1^*$. A DFA for this can have the following transitions: $$(q_0,0)\rightarrow q_0,\ \ (q_0,1)\rightarrow q_1, \ \ (q_1,1)\rightarrow q_1$$

Now by adding a stack we teach this DFA to count. During the inital phase of reading $0$s we add to the stack, during the reading of the $1$'s we pop from the stack. Because the ratio should be $3:1$ we push 1 symbol on the stack for each $0$ and pop three of them for every $1$. So our transitions become: $$(q_0,0,U)\rightarrow (q_0,A),\ \ (q_0,1,AAAU)\rightarrow (q_1,U), \ \ (q_1,1,AAAU)\rightarrow (q_1,U)$$

There are a few more details that you will probably have to take care of:

• PDAs are defined with different kinds of acceptance conditions. Above technique would work with acceptance by empty stack. For other modes, you would have to adjust the construction a bit.
• Your definition of PDA might not allow popping three symbols at a time. Then you would have to find some workaround like coding several stack symbols into one or popping the three in a loop with transitions that do not read input.