you can check if the counter is currently set to 0 by looking for the bottom of the stack. In particular, you can not store a string over an arbitrary alphabet on the stack. For example, the automaton for anbn we have seen in class is a counter automaton. Let L = {w ∈{a, b}∗|w contains the same number of symbols a and b}. (2.a) Build a counter automaton accepting the language L. As in Question 1, describe the algorithm used by your automaton, and draw a transition diagram.
A counter automaton is a pushdown automaton that only uses one stack symbol (in addition
to the bottom of the stack marker). This means that the stack acts as a simple counter: the push operation
increases the counter, the pop operation decreases it, and you can check if the counter is currently set to 0
by looking for the bottom of the stack. In particular, you can not store a string over an arbitrary alphabet
on the stack. For example, the automaton for anbn we have seen in class is a counter automaton.
Let L = {w ∈{a, b}∗|w contains the same number of symbols a and b}.
(2.a) Build a counter automaton accepting the language L. As in Question 1, describe the
used by your automaton, and draw a transition diagram.
(2.b) Write down an accepting computation of your automaton on the string abbbabaa.
Step by step
Solved in 3 steps with 22 images
