Consider languages: L1 = {ww | w in {a,b}*}; L2 = {a^n b^n c^m | n,m = 0}; L3 = {a^m b^n c^n | n,m

Q: What is GATE-CS?

GATE-CS is a competitive examination conducted in India. This question is from the 2022 GATE-CS Theory of Computation paper.

Q: How can I prepare for GATE-CS Theory of Computation?

To prepare for GATE-CS Theory of Computation, practice previous year questions (PYQs), understand concepts thoroughly, and solve mock tests regularly. This 2022 question covers Push-Down Automata (PDA) topic.

Q: What is the difficulty level of this question?

This GATE-CS 2022 Theory of Computation question has a hard difficulty level and is marked as an important question.

Q: Where can I find more GATE-CS previous year questions?

You can find more GATE-CS previous year questions on AspirantMitraa. Browse by subject, topic, year, and difficulty level to practice effectively.

Question

Consider languages: L1 = {ww | w in {a,b}*}; L2 = {a^n b^n c^m | n,m >= 0}; L3 = {a^m b^n c^n | n,m >= 0}. Which of the following statements is/are FALSE?(A) L1 is not CFL but L2 and L3 are DCFL.(B) Neither L1 nor L2 is CFL.(C) L2, L3 and L2 union L3 are all CFL.(D) Neither L1 nor its complement is CFL.

Accepted Answer

Correct Answer: (B), (C), and (D) are FALSEConcept -- Language Classes (from Sipser, Introduction to the Theory of Computation):L1 = {ww | w in {a,b}*}: This is NOT a CFL (proved by pumping lemma for CFLs). L1 is a classic example of a non-context-free language.L2 = {a^n b^n c^m}: This IS a DCFL (and CFL). Push a's, match with b's, then accept any c's. Regular expression-like: a^n b^n (n >= 0) followed by c* is context-free.L3 = {a^m b^n c^n}: Similarly a DCFL (and CFL). Accept any a's, then push b's and match with c's.(A) TRUE: L1 is not CFL (correct), L2 and L3 are DCFL (correct). Statement (A) is true, so it is NOT false.(B) FALSE: Says neither L1 nor L2 is CFL. But L2 IS a CFL. So this statement is false.(C) FALSE: L2 union L3 = {a^n b^n c^m} union {a^m b^n c^n}. The union of two CFLs is CFL. However, L2 union L3 contains strings where you can't determine which rule applies without knowing the partition. The union IS context-free (union of two CFLs is always CFL). So L2, L3, and their union are all CFLs.

Master GATE-CS with Our Test Series

More Questions from Push-Down Automata (PDA)

Frequently Asked Questions

Master GATE-CS with Our Test Series

More Questions from Push-Down Automata (PDA)

Frequently Asked Questions