Consider the following languages:L1 = {wxyx | w, x, y in {0,1}+}L2 = {xy | x, y in {a,b}*, |x| = |y|

Q: What is GATE-CS?

GATE-CS is a competitive examination conducted in India. This question is from the 2020 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 2020 question covers Regular and Context-Free Languages topic.

Q: What is the difficulty level of this question?

This GATE-CS 2020 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 the following languages:L1 = {wxyx | w, x, y in {0,1}+}L2 = {xy | x, y in {a,b}*, |x| = |y|, x != y}Which of the following is TRUE?

Accepted Answer

Correct Answer: (A) L1 is regular and L2 is context-free.Concept -- Language Classification:L1 = {wxyx | w, x, y in {0,1}+}: L1 requires a string that contains at least two occurrences of the non-empty string x with the pattern wxyx. Since x can be any non-empty binary string, and w and y can also be any non-empty strings, the condition wxyx means the string can be decomposed as (w)(x)(y)(x). If x is allowed to be any single character (0 or 1) and w, y any non-empty binary strings, then any binary string of length >= 4 that contains two identical characters at some positions qualifies. The language L1 is actually all binary strings of length >= 4 (for any binary string s of length >= 4, a suitable decomposition exists). This is a regular language (the set of all binary strings with at least 4 characters). More carefully: L1 = {0,1}^* for strings where such a decomposition exists, which is essentially all strings of length >= 4. This is regular.L2 = {xy | x, y in {a,b}*, |x| = |y|, x != y}: L2 is the set of even-length strings over {a,b} where the first half differs from the second half. This is context-free: a PDA can guess the midpoint, push the first half, and compare with the second half, checking that at least one position differs. L2 is not regular (it requires matching lengths), but it is a CFL.

Consider the following languages:L1 = {wxyx | w, x, y in {0,1}+}L2 = {xy | x, y in {a,b}*, |x| = |y|, x != y}Which of the following is TRUE?

Master GATE-CS with Our Test Series

More Questions from Regular and Context-Free Languages

Frequently Asked Questions

Consider the following languages:L1 = {wxyx | w, x, y in {0,1}+}L2 = {xy | x, y in {a,b}*, |x| = |y|, x != y}Which of the following is TRUE?

Master GATE-CS with Our Test Series

More Questions from Regular and Context-Free Languages

Frequently Asked Questions