GATE CSE 2019 | Question: 7

Question

If $L$ is a regular language over $\Sigma = \{a,b\} $, which one of the following languages is NOT regular?

• A. $L.L^R = \{xy \mid x \in L , y^R \in L\}$
• B. $\{ww^R \mid w \in L \}$
• C. $\text{Prefix } (L) = \{x \in \Sigma^* \mid \exists y \in \Sigma^* $such that$ \ xy \in L\}$
• D. $\text{Suffix }(L) = \{y \in \Sigma^* \mid \exists x \in \Sigma^* $such that$ \ xy \in L\}$

Answer 1

$ww^R$ is well known CFL - the PDA can non-deterministically determine the middle position of the string and start popping (this is not DCFL though).

Reverse, Suffix, Prefix, Concatenation of Regular(s) is Regular. Answer is (B).

Comments

I can Understand Option B is not Regular.

But, can Someone pls clarify why Option A can’t be non-Regular too ?

 

Thanks in advance

---

I think it is already explained in the answer…

Reverse, Concatenation operations on Regular(s) is Regular.

option A is a concatenation of regular and its reverse, therefore it is a regular language

---

Draw Finite Automata for L   
then Interchange states
intial to final
and
final to initial 

then

concatenate 
L with L^R using Epsilon 

Answer 2

option B. is CFL

all others are regular

Answer 3

A simple point where one can easily miss out is in L.L^R it is given L and L^r are different strings belonging to L(x and y^R) whereas in option B it is the same string concatenated with reversed (wR).

That's why A is regular and B is CFL

Answer 4

$L$ is given as regular so, $L^r$ is regular so,$L.L^r$ is regular

but $W.W^r$ is CFL so, ans is B

Comments

Same thing can happen in B) too. right?

---

option a has a language ,so if a language is regular then its reverse is also regular so concatenation is also regular

option b has a string and its reverse so it belongs to problem of string matching therefore it is cfl

---

I am not able to differentiate between option A and Option B. I got the example for option B. Can someone provide example for option A?

if L= {ab}

then in option A → it becomes ab.ba= abba

 In option B also abba possible.

For both the cases stack is needed.