34 votes 34 votes If $L$ is a regular language over $\Sigma = \{a,b\} $, which one of the following languages is NOT regular? $L.L^R = \{xy \mid x \in L , y^R \in L\}$ $\{ww^R \mid w \in L \}$ $\text{Prefix } (L) = \{x \in \Sigma^* \mid \exists y \in \Sigma^* $such that$ \ xy \in L\}$ $\text{Suffix }(L) = \{y \in \Sigma^* \mid \exists x \in \Sigma^* $such that$ \ xy \in L\}$ Theory of Computation gatecse-2019 theory-of-computation regular-language 1-mark + – Arjun asked Feb 7, 2019 • edited Nov 30, 2022 by Lakshman Bhaiya Arjun 15.0k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 45 votes 45 votes $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). Digvijay Pandey answered Feb 7, 2019 • edited May 13, 2019 by Krithiga2101 Digvijay Pandey comment Share Follow See all 12 Comments See all 12 12 Comments reply Show 9 previous comments MohanK commented Dec 9, 2020 reply Follow Share 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 0 votes 0 votes Abhineet Singh commented Dec 10, 2020 reply Follow Share 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 4 votes 4 votes bluesta commented Jan 27 reply Follow Share Draw Finite Automata for L then Interchange states intial to final and final to initial then concatenate L with L^R using Epsilon 0 votes 0 votes Please log in or register to add a comment.
3 votes 3 votes option B. is CFL all others are regular Naveen Kumar 3 answered Feb 7, 2019 Naveen Kumar 3 comment Share Follow See all 0 reply Please log in or register to add a comment.
3 votes 3 votes 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 Accel_Blaze answered Feb 3, 2021 Accel_Blaze comment Share Follow See all 0 reply Please log in or register to add a comment.
2 votes 2 votes $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 Dharmendra Tiwari answered Feb 7, 2019 • edited May 25, 2019 by akash.dinkar12 Dharmendra Tiwari comment Share Follow See all 7 Comments See all 7 7 Comments reply Show 4 previous comments srestha commented Nov 18, 2019 reply Follow Share Same thing can happen in B) too. right? 1 votes 1 votes Winner commented Dec 28, 2019 reply Follow Share 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 0 votes 0 votes Yor commented Jun 4, 2021 reply Follow Share 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. 0 votes 0 votes Please log in or register to add a comment.