FSM that only accepts strings w/ equal number of 1's and 0's

  • Thread starter goraemon
  • Start date
  • Tags
    Strings
In summary, it is impossible to construct a finite state machine that accepts only strings in the format 0^n 1^n, where n is an arbitrary finite number. However, it is possible to construct a finite state machine that accepts only strings with an equal number of zeros and ones, which can then be used to validate strings in the format 0^n 1^n. This can be achieved by keeping track of the count of consecutive 0's in the prefix of a given string and ensuring that it equals the count of consecutive 1's in the suffix of that string. The existence of a FSM that can do this can be assumed, although it is not possible to actually construct one.
  • #1
goraemon
67
4
Thread moved from the technical forums, so no HH Template is shown.
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.
 
Physics news on Phys.org
  • #2
goraemon said:
This is impossible, since by definition a FSM has no counter or memory.
You do not need a counter or memory (besides the "memory" of the current state) to do this. But you don't have to care about this part: you can assume that such a machine exists here.
goraemon said:
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.
You do not have a counter. And you do not need one. You need some other way to validate the input.
 

FAQ: FSM that only accepts strings w/ equal number of 1's and 0's

What is a FSM?

A FSM (Finite State Machine) is a mathematical model used to describe a system that can be in one of a finite number of states at any given time.

What is a string in a FSM?

In a FSM, a string is a sequence of symbols that can be read by the machine and used to transition between states.

What does it mean for a FSM to only accept strings with an equal number of 1's and 0's?

This means that the FSM will only accept strings that have an equal number of 1's and 0's in them. For example, the string "0101" would be accepted, but "0110" or "001" would not be accepted.

What happens if a string with an unequal number of 1's and 0's is entered into the FSM?

If a string with an unequal number of 1's and 0's is entered, the FSM will reject the string and remain in its initial state, as it is not a valid input for the specified language.

Can a FSM only accept strings with equal number of 1's and 0's or can it also accept other types of strings?

A FSM can be programmed to accept any type of string, but in this specific case, it has been designed to only accept strings with an equal number of 1's and 0's. Other FSMs can be designed to accept different types of strings based on their specific language.

Similar threads

Back
Top