For each state of the PDA, indicate whether that state’s outward transitions for
ID: 3845020 • Letter: F
Question
For each state of the PDA, indicate whether that state’s outward transitions form a deterministic set of moves or a nondeterministic set of moves. Identify each set of transitions out of a state that cause the machine to be nondeterministic. Briefly explain why that combination of transitions leaving that state is not deterministic in terms of the definition of the deterministic moves of a DPDA in the text
b,a q3 91 45 a, a b,Er FIGURE 2.17 State diagram for PDA M2 that recognizes i,j, k 0 and i J orExplanation / Answer
Answer:
A pushdown automaton (PDA) is a finite state machine which has an additional stack storage. The transitions a machine makes are based not only on the input and current state, but also on the stack.
The textbook defines DPDAs (Deterministic PDAs) and DCFLs (Deterministic CFLs) in the introductory part of section 3.7. According to the textbook's definition, a DPDA is a PDA in which no state phas two different outgoing transitions
which are compatible in the sense that both could be applied. A DCFL is basically a language which accepted by a DPDA, but we need to qualify this further.
We want to argue that the language L = { w {a,b}* : #a(w) = #b(w)} is deterministic context free in the sense there is DPDA which accepts it.
In the above PDA, the only non-determinism is the issue of guessing the end of input; however this form of non-determinism is considered artificial. When one considers whether a language L supports a DPDA or not, a dedicated end-of-input symbol is always added to strings in the language.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.