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: 

Responses

More Comments
sudsho's picture

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

hradeshpatel's picture

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.

sumitverma's picture

Here w is a word not an entire language. I do not know you all are taking w as (0+1)* and mixing other thing with this.
Answer given is correct. Both Extend(L,w) and Shrink(L,w) are regular.

for extend, we know concat of two reg strings is regular so

if xw belongs to regular

x is reg and w is reg

Did not found what you are looking for, Ask your doubt or Help by your contribution

Enter your search keyword:

Search form

Wait!

Here is a chance to join biggest community of technical Students,
Tutors with FREE learning resources and so much more.
It takes less then 60 seconds.