Question

consider the set of all binary strings such that every pair of adjacent 0 's appears before any pair of adjacent 1's.prove that this is a regular language by giving a regular expression for this.​

Answer 1

Explanation:

individually,So

$R(L)=R(L1)R(L2)$

where $L1$ is the language of all strings that do not contain any pair of 1’s and

$L2$ is the language of all strings that do not contain any pair of 0’s.

$R(L1)=(0+10)^{*}(1+\epsilon )$. and

$R(L2)=(1+01)^{*}(0+\epsilon )$

So $R(L)=(0+10)^{*}(1+\epsilon )(1+01)^{*}(0+\epsilon )$.

After simplifying the regular expression,

$R(L)=(0+10)^{*}(1+01)^{*}(0+\epsilon )$.

NFA for above language will be,



Required DFA will be