Are the following True or False. In either case, provide a justification for you

Question

Are the following True or False. In either case, provide a justification for your answer.

a) any NPDA can be transformed into an equivalent DPDA

b) Any DPDA can be transformed into an equivalent NPDA

c) Like the string pumping lemma for regular languages, the strong pumping lemma for context-free languages allows us to only consider partitions involving the first p symbols (where p is the pumping length).

d) The stack of a PDA can be empty at the start and stop of processing, but will always have at least one symbol on the stack at intermediate times.

Explanation / Answer

a) any NPDA can be transformed into an equivalent DPDA

ANs: False, NPDA are more powerful than DPDA

b) Any DPDA can be transformed into an equivalent NPDA

Ans: True, DPDA are subset of NPDA

c) Like the string pumping lemma for regular languages, the strong pumping lemma for context-free languages allows us to only consider partitions involving the first p symbols (where p is the pumping length).

Ans: True

d) The stack of a PDA can be empty at the start and stop of processing, but will always have at least one symbol on the stack at intermediate times.

Ans: True., because Alphabets of language can not be empty, so hence we will be having someting to process in intermediate

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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