At the top of your solutions, be sure to write down the names of anyone you discussed this assignment with or any resources you used!
Please copy the description of the problem as well as your solution.
Submit your written work through Gradescope. Refer to Tools for details on using both.
You may find it useful that all problems from the Sipser's Theory of Computation (2nd edition) can be found here.
For the language in Exercise 2.6b (Refer to Sipser, 2nd edition, pages 129-130)
create a pushdown automaton using the automaton simulator and provide:
an informal description of your machine/approach
the state diagram
the plaintext description from the automaton simulator
for the PDA you create, you should:
perform bulk tests using the automaton simulator
ACCEPT:
aabbb
aaab
abb
bba
aba
ba
a
b
REJECT:
aabb
ab
ε
give an example of one string in the language (of length at least 3) and the PDA's computation of it ending in an accept
the computation should be in the format:
(state, remaining input, stack with bottom of stack at the left) →symbol read
refer to this slide for an example
For the language in Exercise 2.6d (Refer to Sipser, 2nd edition, pages 129-130)
create a pushdown automaton using the automaton simulator and provide:
an informal description of your machine/approach
the state diagram
the plaintext description from the automaton simulator
for the PDA you create, you should:
perform bulk tests using the automaton simulator
ACCEPT:
ε
a
aba
ab#bba#aab#abb#aabbb
ab#baab#bba
bba#ababab#ba#abb
#
ab##bba
REJECT:
ab#ab
ab#bba
ba#baba#aab
bba#ababab#ba#aab
aab#aabbbb#abababaa#bbaabbba
give an example of one string in the language (of length at least 3) and the PDA's computation of it ending in an accept
the computation should be in the format:
(state, remaining input, stack with bottom of stack at the left) →symbol read
refer to this slide for an example
Use the procedure given in Theorem 2.20 to convert the following grammar into an equivalent PDA. That is, construct a pushdown automaton that accepts the language generated by G using the algorithm given in the proof of Lemma 2.21.
G = (V, Σ, R, S) that generates the language 0n1n, where
V = { S }
∑ = { 0,1 }
R = { S → 0 S 1 | ε }
From Sipser, 2nd edition (page 131):
2.31