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

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

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)*

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

Enter your search keyword:

Search form


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.