2

I am trying to understand why the language {0^n1^n | n >=0} is not regular.

I understand that FSA's do not have memory and therefore can not keep track of what the value of n is, however, if the machine is able to generate enough states for 0 why can it not generate enough states for 1.

Does it just lose the memory of n?

I hope somebody can explain this to me.

Is 0^n also not regular? Since there is no memory of n?

  • "if the machine is able to generate enough states for 0" - what do you mean by "the machine is able to generate enough states for 0", and why do you think it's true? – user2357112 Feb 22 '17 at 02:39
  • http://stackoverflow.com/questions/2309752/why-is-anbn-n-0-not-regular - This thread led me to believe that the FSA could generate enough states for 0. If this is not true then would `0^n`, be nonregular? And if so, why do textbooks use the `{0^n1^n | n >=0}` example? –  Feb 22 '17 at 02:40
  • 1
    Again, what do you actually mean by that? FSAs cannot "generate" states. What part of that link made you think that the quoted statement was meaningful and true? – user2357112 Feb 22 '17 at 02:42
  • I mean, can the FSA accept a string with an arbitrary number of 0's? –  Feb 22 '17 at 02:43
  • Not helpful @JimD. I have already looked at the thread. I want to know why `0^n` is regular and `{0^n1^n | n >=0}` is not regular. If an FSA can not keep track of how many states it has traveled then how is `0^n` regular? –  Feb 22 '17 at 02:44
  • 1
    A finite state automaton can distinguish between strings in `{0^n | n >= 0}` and strings not in that set. That's simple enough; it only needs two states, "I have only seen zeros" and "I have seen some other character". It cannot distinguish between strings in `{0^n1^n | n >=0}` and strings not in that set; it would need an infinite number of states to do that. – user2357112 Feb 22 '17 at 02:48
  • 1
    you don't have to keep track of anything other than whether you have seen a zero or anything else to accept a string of 0s. Start state goes to final state with a 0, final state goes to final state on 0, final state goes to dead state on anything else. – JimD. Feb 22 '17 at 02:48
  • user2357112 and Jim D. This makes much more sense now. Thank you! Both your comments solved my question. If either of you post a solution I will accept it. –  Feb 22 '17 at 02:52

0 Answers0