Given a set A ⊆ {0, 1}*, let A' = {x...

Given a set A ⊆ {0, 1}*, let
A' = {xy | x1y ∈ A}. That is, A' consists of all the strings obtained from a string in A by deleting in A by deleting exactly one 1. If A is regular, then A' is

(A) Regular

(B) Context free but not regular

(C) Recursive but not context free

(D) None of the above

sumitverma's picture
Sumit Verma @sumitverma 1 Dec 2016 04:04 pm

Let M be a DFA accepting A. Now, add an ε-transition for each transition due to 1, e.g. let δ(p, 1) = q, then add another transition δ(p, ε) = q. This will give an NFA which will accept A'. Therefore, A' is regular.

ananyamukherjee's picture
Ananya Mukherjee @ananyamukherjee 2 Dec 2016 09:37 pm

u ean to say regular- x= regular.

Because we canrepresent x1y as (0+1)*1(0+1)*

now we are subtracting 1

and getting finally (0+1)*(0+1)*