1
$\begingroup$

I have the following question

enter image description here

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?

$\endgroup$
  • 2
    $\begingroup$ This is not sufficient as a proof, and adding a picture or two will not help. *Hint: Have you hear about the Pumping lemma? en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages $\endgroup$ – Ove Ahlman Dec 1 '15 at 14:07
  • $\begingroup$ @OveAhlman Yeah.But pumping lemma a negativity test.I dont think i need to use it unless a pattern is involved.Its not really necessary.The question is not proving-its stating and is just for 6 marks.Please correct me if im wrong :) $\endgroup$ – techno Dec 1 '15 at 14:09
  • $\begingroup$ Well, that depend on how picky your teacher is. However since "justify your answer" is there I would say you need to use pumping lemma (or equivalent theorems) to show that it is not regular. Right now your motivation does not prove anything. $\endgroup$ – Ove Ahlman Dec 1 '15 at 14:11
  • 1
    $\begingroup$ @Ove: I don't understand the fixation people have on the pumping lemma for this kind of questions. The Myhill-Nerode theorem is much easier to apply and more precise too. In my opinion the only thing the pumping lemma has going for it is a memorable name. $\endgroup$ – Henning Makholm Dec 1 '15 at 14:12
  • $\begingroup$ @OveAhlman hmm..okay $\endgroup$ – techno Dec 1 '15 at 14:14
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The only thing you add with to my reasoning here is that "automaton cannot be allowed to be in the same state after having read runs of 0s of two different lengths" .Is that enough for justification .. do i need to use myhill nerode? BTW its actually Zero One and O( oe) $\endgroup$ – techno Dec 1 '15 at 14:21
  • 1
    $\begingroup$ @techno: It is so close to the argument inside Myhill-Nerode that I don't think an explicit invocation of it is necessary. But in classwork I would certainly include that line you quote -- which is what shows that you understand how the handwavy "finite memory" connects to the actual automata formalism. $\endgroup$ – Henning Makholm Dec 1 '15 at 15:16
  • 1
    $\begingroup$ @HenningMakholm maybe you can help me with this question: math.stackexchange.com/questions/1556534/… Thanks $\endgroup$ – John Smith Dec 2 '15 at 21:22
0
$\begingroup$

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$$


$\endgroup$
  • $\begingroup$ Thanks for your answer.I have not seen Pumping Lemma in detail.. will get back after i take a look. $\endgroup$ – techno Dec 1 '15 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.