1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Feb 22, 2016 #1
    • 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.
  2. jcsd
  3. Feb 22, 2016 #2


    User Avatar
    2017 Award

    Staff: Mentor

    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.
    You do not have a counter. And you do not need one. You need some other way to validate the input.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted