Question

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

• A. Prefix (L) = $\{xϵ{\sum }^{\ast }\mid \exists yϵ{\sum }^{\ast }suchthatxyϵL\}$
• B. Suffix (L) = $\{yϵ{\sum }^{\ast }\mid \exists xϵ{\sum }^{\ast }suchthatxyϵL\}$
• C. $\{w{w}^R\mid wϵL\}$
• D. $L\cdot L^R\{xy\mid xϵL,y^RϵL\}$

Answer 1

The correct option is C $\{w{w}^R\mid wϵL\}$

If L is regular, $L\cdot L^R$ is also regular by closure property.

Suffix(L) and Prefix(L) are also regular by closure property.

However option (d) $\{w{w}^R\mid wϵL\}$ need not be regular since if L is an infinite regular language then $\{w{w}^R\mid 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.

So answer is option (d).