Question

State true or false:

Statement: Counter Automaton can exist for the language L={0^i1^i|i>=0}

(a) Statement: Counter Automaton can exist for the language L={0^i1^i|i>=0}

(b) true

(c) false

The question was posed to me in final exam.

This interesting question is from From Grammars to Push Down Automata topic in division Push Down Automata of Automata Theory

Answer 1

The correct answer is (a) Statement: Counter Automaton can exist for the language L={0^i1^i|i>=0}

The explanation: The PDA works as follows. Instead of saving excess 0’s or 1’s on the stack, we save *’s and use two different states to indicate which symbol there is currently a surplus of. The state q0 is the initial state and the only accepting state.