Question: Suppose you have a finite state machine that accepts only strings with an equal number of zeros and ones. Show that you can then construct a finite state machine that accepts only strings of the form 0^n 1^n, i.e., an arbitrary finite number of zeros followed by the same number of ones.

My attempt at a response:

A Finite State Machine that accepts strings with an equal number of 0’s and 1’s (e.g. n zeros and n one's, where n is some arbitrary finite number), must have a counter that keeps track of the total number of 0's and 1's. This is impossible, since by definition a FSM has no counter or memory. But suppose this were possible. Then it’d be possible to construct another FSM that keeps track of the count of consecutive 0's in the prefix of a given string, and ensure that number equals the count of consecutive 1's in the suffix of that string.

I feel like there is more to the answer than this, but I don't really know what else can be said. I know that no FSM can be constructed to accept only strings in the format 0^n 1^n where n could be any arbitrary nonnegative integer, but that it is possible to do for any fixed, specific value of n. For example, it's possible to build FSM to accept only strings that contain three 0's, followed by three 1's. But I don't know whether this detail is relevant at all. Thanks for any help.

  • $\begingroup$ "By definition a FSM has [no memory]" - yes it does, it has the current state! $\endgroup$
    – user253751
    Feb 22 '16 at 23:27

The question is not really well-defined since there is no FSM that accepts your language $L$, so the existence of such an FSM implies anything – for example, $2+2=3$.

However, the intended solution was to notice that $$ L \cap 0^*1^* = \{0^n1^n : n \geq 0\}. $$ Since the regular languages are closed under intersection, this shows that an FSM for $L$ can be converted to one of $\{0^n1^n : n \geq 0\}$.

Your attempt claims that an FSM accepting $L$ must have a counter. This is not a formal statement: it has no formal content. It's just intuition. A PDA for $L$ also doesn't have a counter; it has a stack. Counter is not a well-defined technical notion.

  • $\begingroup$ See here for lots of examples of abstract machines with counters. $\endgroup$ Feb 22 '16 at 21:34
  • $\begingroup$ @RickDecker Of course it is possible to define an alternative machine with a counter. The point is that an FSM isn't one of them. This means the OP is referring to some vague notion of an FSM "having" a counter by some indirect mechanism. This is not a well-defined concept. $\endgroup$
    – Erick Wong
    Feb 25 '16 at 22:34

Step 1: Show this finite state machine does not exist

Step 2: P∧¬P→Q

Elaboration on step 1: For any number of states in the machine N there is a number of consecutive zeros N+1 that it cannot distinguish from another number of consecutive zeros M. Therefore, the machine will will match M zeros followed by N ones which it should not.


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.