1

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?

techno
  • 639
  • 2
    This is not sufficient as a proof, and adding a picture or two will not help. *Hint: Have you hear about the Pumping lemma? https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages – Ove Ahlman Dec 01 '15 at 14:07
  • @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 :) – techno Dec 01 '15 at 14:09
  • 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. – Ove Ahlman Dec 01 '15 at 14:11
  • 1
    @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. – hmakholm left over Monica Dec 01 '15 at 14:12
  • @OveAhlman hmm..okay – techno Dec 01 '15 at 14:14
  • @HenningMakholm I'd say that the point with the pumping Lemma is that it is very similar in the case of context free languages, thus if you have understood one you probably can figure out the other. I dont know if there is a similiar theorem as Myhill-Nerode for context free languages. – Ove Ahlman Dec 01 '15 at 15:04
  • @OveAhlman: Hmm, that does make an amount of sense. – hmakholm left over Monica Dec 01 '15 at 15:17

2 Answers2

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.

hmakholm left over Monica
  • 286,031
  • 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) – techno Dec 01 '15 at 14:21
  • 1
    @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. – hmakholm left over Monica Dec 01 '15 at 15:16
  • 1
    @HenningMakholm maybe you can help me with this question: http://math.stackexchange.com/questions/1556534/triangle-formula-for-alternative-points Thanks – John Smith Dec 02 '15 at 21:22
0

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

user2879934
  • 855
  • Thanks for your answer.I have not seen Pumping Lemma in detail.. will get back after i take a look. – techno Dec 01 '15 at 15:48