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\}$

Comments

idea to make dfa for option d :https://math.stackexchange.com/questions/304379/suffix-regular-language

---

https://courses.grainger.illinois.edu/cs374/fa2018/slides/05-nfa-reg-lang-closure.pdf

---

L.L^R is simlar to L ^ L^R, regular is closed in both intersection and complement , so it is closed here also

ww^R is palindrome string which is a well known CFL which is not regular

prefix is similar to duke set or balancing parenthesis problem of DSA done using stack

here, in duke set, for any string like '(()())()', # of opening brackets>= closing brackets for every prefix

similar is for suffix also

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 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 

---

because regular languages are closed under reverse and concatenation operation .

 

Answer 2

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 3

option B. is CFL

all others are regular

Answer 4

ww^R cannot be recognized without using stack, so it cannot be regular.

Answer 5

$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

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.

---

@Yor, Take L = {ab,ba} for option A and check whether it is same as option B or not.