##### Let Σ = {a, b}. Given a language L ⊆ Σ* and a ...

Let Σ = {a, b}. Given a language L ⊆ Σ* and a word w ∈ Σ* , and the languages:

Extend(L, w) := { xw | x ∈ L }

Shrink(L, w) := { x | xw ∈ L }

If L is regular,

(A) both Extend(L,w) and Shrink(L,w) are regular. | |

(B) both Extend(L,w) and Shrink(L,w) are not regular. | |

(C) Only Extend(L,w) is regular. | |

(D) Only Shrink(L,w) is regular. |

Hint:

<div class="tex2jax"></div>

If L is regular, there exists a regular expression r whose language equals L. The word w is a singleton language and can be represented by the regular expression w. Then, Extend(L, w) is the language given by the expression r.w. Hence Extend(L, w) is regular.

If L is regular, there is a deterministic finite automaton (DFA) A whose language is L. Mark all states q in this DFA such that reading w from q leads to an accepting state of A. Call this set of states F

_{new}. The required DFA for Shrink(L, w) would have the same states, transitions and initial states as A. However, the set of accepting states would be F_{new}.But we can have a counter example for shrink operation..

Say we have L = (0+1)*

and it is already given w ∈ (0+1)* if we consider {0,1} as alphabet..Let L = {0+1}* .. Then let

x = 0

^{n}1^{n }so we havexw = 0

^{n}1^{n }. (0+1)* | n >= 0which is = (0 + 1)* by keeping n = 0 and hence xw ∈ L and hence the requirement of the language is satisfied..

But x is not regular as it is a CFL..As we have given here a valid counter example..And shrink is producing x only..Hence we are getting a contradiction about regularity of shrink() operation..

Hence only extend should be regular..Hence C) should be the correct option..we cant take x as 0

^{n}1^{n }by ourself...after shrinking from the xw only x is left...^{ }...counting is not possible here...plz got option C is correct

Suppose w is a^nb^n and according to extend does concatenation of regular x (given x belongs to L which is regular) with w (which is CFL according to assumption here) , so extend cannot be regular.

Regarding Habib's comment on shrink, i would say its a trivial case only as every language( be it regular, CFL or CSL) all have a regular superset (a+b)* and a regular subset as fi ( or null). According to me answer should be D( if ignoring the trivial case) otherwise it can be B. @sumit sir , plz figure this out.