Skip to content
GATEiit

GATE CSE 2020 Q42: Classify L1 = {wxyx} and L2 = {xy : |x| = |y|, x ≠ y}

Question

Consider the following languages.

L1={wxyx∣w,x,y∈(0+1)+}L_1 = \{wxyx \mid w, x, y \in (0 + 1)^+\} L2={xy∣x,y∈(a+b)∗,∣x∣=∣y∣,x≠y}L_2 = \{xy \mid x, y \in (a + b)^*, |x| = |y|, x \ne y\}

Which one of the following is TRUE?

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 2/3 mark in GATE.
Show answer and explanation

Answer: A (official GATE 2020 final answer key)

Concept used: Since xx can be a single symbol, L1L_1 collapses to a simple pattern; L2L_2 is the classic CFL of even-length strings whose halves differ.

First step: Take ∣x∣=1|x| = 1: L1L_1 is all strings of length at least 4 whose last symbol also occurs at position 2 or later, before the second-last position; write it as a regular expression.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2020 CS question paper and final answer key, organised by IIT Delhi. Question paper · Answer key

More Theory of Computation PYQs

PracticePractise Theory of Computation questions →Full paperAll GATE CSE 2020 questions →