GATE Computer Science (CS) 2019 Solved Papers

Question : 17 of 65

Marks: +1, -0

L

is a regular language over

\Sigma=\left\{a_{t}\right\}

, which one of the following languages is NOT regular?

$L ⋅ L^{R}=\{x y ∣ x ∈ L, y^{R} ∈ L\}$
$\{w w^{R} ∣ w ∈ L\}$
Prefix $(L)=\{x ∈ Σ ⋅ ∣ ∃ y ∈ Σ *$ such that $x y$ $∈ L\}$
Suffix $(L)=\{y ∈ Σ^{*} ∣ ∃ x ∈ Σ *$ such that $x y$ $∈ L\}$

Validate

Solution:

{L}

is regular,

{L} ⋅ {L}^{ {R}}

is also regular by closure property.
Suffix (L) and Prefix (L) are also regular by closure property.
However option (b)

\{ {wW}^{ {R}} ∣ {w} ∈ {L}\}

need not be regular since if

{L}

is an infinite regular language, then

\{w w^{R} ∣ w ∈ L\}

will not only be infinite, but also non-regular. Since it involves string matching and we can increase in length indefinitely and then finite automata FA will run out of memory.

Go to Question:

Prev Question

Next Question