edited by
14,689 views
34 votes
34 votes

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

  1. $L.L^R = \{xy \mid x \in L , y^R \in L\}$
  2. $\{ww^R \mid w \in L \}$
  3. $\text{Prefix } (L) = \{x \in \Sigma^* \mid \exists y \in \Sigma^* $such that$ \ xy \in L\}$
  4. $\text{Suffix }(L) = \{y \in \Sigma^* \mid \exists x \in \Sigma^* $such that$ \ xy \in L\}$
edited by

5 Answers

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

edited by
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
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
edited by
Answer:

Related questions

49 votes
49 votes
6 answers
1
Arjun asked Feb 7, 2019
33,886 views
For $\Sigma = \{a ,b \}$, let us consider the regular language $L=\{x \mid x = a^{2+3k} \text{ or } x=b^{10+12k}, k \geq 0\}$. Which one of the following can be a pumping...
21 votes
21 votes
7 answers
2
Arjun asked Feb 7, 2019
9,033 views
The expenditure on the project _____ as follows: equipment Rs.$20$ lakhs, salaries Rs.$12$ lakhs, and contingency Rs.$3$ lakhs.break downbreakbreaks downbreaks
11 votes
11 votes
6 answers
3
Arjun asked Feb 7, 2019
5,678 views
The search engine’s business model ____ around the fulcrum of trust.revolvesplayssinksbursts
8 votes
8 votes
4 answers
4