Checking whether a Language is Regular

Question

I have the following question

My approach in solving this problem would be.

For a language to be regular we should be able to create a Finite Automata that could accept it.In the above example n and m is unbounded.Finite Automata only have finite memory.Since in this case it would be required to count the number of 0s(zeroes) and Os and accept only if it matches finite automata would require an infinte memory.So this langauge is not accepted by FA and hence is not regular.

Is my approach correct do i need to add some additional figures to complete the answer?

Answer 1

Your idea is right, but it is probably slightly too handwavy to count as an actual proof.

What you should do here is to add an explicit argument that the automaton cannot be allowed to be in the same state after having read runs of 0s of two different lengths, because the sets suffixes that should be accepted after $\mathtt 0^a$ and $\mathtt 0^b$ are not the same. Since there are infinitely many different runs of 0s you would need to distinguish, the automaton would need infinitely many states, which is not allowed for a DFA.

This reasoning is neatly encapsulated by the Myhill-Nerode theorem, which in most cases is much easier to apply than the pumping lemma for regular languages.

Answer 2

Let $$x={0^p}{1^q}{0^p}$$ So in the pumping lemma

$u={0^s}$ $v=0^{k}$ $w={10^r}$ $$s+k=r$$ pump on $i=0$

$$s-k \neq r$$

---