3) [5] True or False: i) --LREG= LNPDA (i.e., the set of languages accepted by n

Question

3) [5] True or False: i) --LREG= LNPDA (i.e., the set of languages accepted by nondeterministic pushdown automata is the regular languages.) ii _Given an arbitrary context-free language L, it is possible to make a deterministic Turing machine to accept L. iii)_LDTM:LREC (i.e., the set of languages accepted by Turing machines is the decidable languages.) v)NFLoFa (i.e, the set of languages accepted by deterministic finite automata is a proper IV subset of the languages accepted by nondeterministic finite automata.) v) --LDPDA = Lcr(ie, the set of languages accepted by deterministic pushdown automata is the context-free languages.)

Explanation / Answer

Solution:-

1. False. Because non-deterministic pushdown automata accepts or recognize all context-free languages.

2. True. Because there are some turing machine exists which can simulate the non-deterministic pushdown automata and accept the arbitrary context free language.

3. True. Because if turing machine TM exists on input I, TM accepts if I belongs to the language. These languages are called decidable languages.

4. False. Because set of languages (L1) accepted by DFA and set of languages (L2) accepted by NFA both are equal. (L1 = L2)

5. False. Because set of languages accepted by deterministic pushdown automata are deterministic context-free languages. Not all context-free languages are deterministic.

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

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