in Theory of Computation
341 views
0 votes
0 votes

Identify whether the language is regular or not and plz justify the ans. 

in Theory of Computation
341 views

1 Answer

5 votes
5 votes
Best answer

1)First one is regular

 the Language is ={0000,00100,00000,000100,…..}

We can write the regular expression =$00(1+0)^{*}00$ as $u\in \Sigma ^{*}$ which can eat up all the strings in between . The language contain all the string which start and end with $00$.

  2)   It is not regular language.

proof by myhill – nerode theorem:-

$L=\left \{ 0^{k}1u0^{k} |k>1\wedge u\in \sum ^{*}\right \}$

Consider the infinite set of strings

$S=\left \{ 0^{k}1 |k\geq 1 \right \}$

Claim $S$ is distinguishing set for L.

Take any pair of string $\left ( 0^{k}1,0^{j}1 \right )$ of strings where $j\neq k$.

Let $z=0^{k}$

Then $z=0^{k}10^{k}$ is in L but $z=0^{j}10^{k}$ is not in L.

So all pairs of strings in S are distinguishable to L.

Hence there are infinitely many equivalence of $\equiv _{L}$, so L is not regular .

https://people.csail.mit.edu/rrw/6.045-2020/lec6-color.pdf

selected by

2 Comments

@Deepak Poonia sir is this proof corret sir ?

0
0
Thanks , for the explanation.
0
0