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

Sumit Verma sumitverma 1 Dec 2016 03:47 pm

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

Habib Mohammad Khan habibkhan 1 Dec 2016 08:14 pm

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 = 0n 1n  so we have

xw =  0n 1. (0+1)* | n >= 0

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

Shobhit sudsho 2 Dec 2016 12:38 am

we cant take x as 0n 1n by ourself...after shrinking from the xw only x is left... ...counting is not possible here...

Hradesh hradeshpatel 1 Dec 2016 10:46 pm

plz got option C is correct

Vishwajit kumar vishnu vishwajitvis 2 Dec 2016 12:23 am

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.