Is the language regular

66 Views Asked by At

We have to check, if the given two languages are regular or not.

L={w |each prefix of w has more 0 than 1}

L'={w|w has a prefix with more 0 than 1}.

I tried something like this:

If L regular, than there has to be an n -> length of any string longer than n can be composed as string=$xy^iz$ , i $\in N$. I choose string =$0^{p+1}1^p \in L$.

Because of |xy|<=p, y has to be a substring of 0s.So $xy^iz$ cannot be in L, because $xy^0z$ has at least one zero less. The atribute of L is not satisfied. Does it make any sense? And what is the difference to L'? Could I not just use the same argumentation?

1

There are 1 best solutions below

3
On BEST ANSWER

Your pumping lemma argument for $ L $ makes sense, with the exception that you switch between using $ p $ and $ n $ for the pumping length.

The same word doesn't work for $ L' $ though - your word can be split into $ x = \epsilon, y=0, z=0^p1^p $. Then $ xy^iz = 0^{p+i} 1^p $ is in $ L' $ (since it has the prefix $ 0 $ which has more $ 0 $s than $ 1 $s).

You can instead try the word $ 1^{p} 0^{p+1} \in L' $. Then $ y $ is all $ 1 $s and $ xy^2z \notin L' $.