[Solved]: Finite State Machine that only accepts strings with equal number of 0's and 1's

Problem Detail: 

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.

Asked By : user3280193

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/53481