3. (10 points) Consider the PDA over the input alphabet 0,1 with the state diagr

Question

3. (10 points) Consider the PDA over the input alphabet 0,1 with the state diagram qo q1 a. What is the stack alphabet, ?, for this PDA? b. From which states might a computation of this PDA make a move that doesn't consume input and doesn't push anything onto the stack? c. From which states might a computation of this PDA make a move that doesn't change the contents of the stack? d. At the end of a successful computation of this PDA on a string w, can the stack be nonempty? e. Is the string E accepted by this PDA? f. Is the string 01 accepted by this PDA? g. Is the string 110 accepted by this PDA? h. Is the string 0110 accepted by this PDA? i. For all strings w, if w is accepted by this PDA, is wR guaranteed to be accepted by the PDA as well? j. Is the language of this PDA infinite?

Explanation / Answer

a.Stack element is not an input symbol or variable but the elemnent which is used as base of stack.(example $)

b.q1 to q2 on seeing 1 we push epsilon i.e. nothing

c.q2 to q3 no operaation performed only at top $.

d.No if stack is containing anything except $ after transition, means the word do not belong to that language.

e.No as on epsilon, no motion from q1 to q2 so epsillon can't reach final state/

f.Yes.move from q1 to q2 then q3 to q4

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.