Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Question about Finite State Automatons

  1. Oct 11, 2012 #1
    I'm reading about automata theory and am currently at the part about what a FSA can recognize and what it cannot. They use the example of some language: {0n1n | n ≥ 0} which an FSA cannot be built for.

    When I first started learning about state machines before reading into theory of computation was from the Mealy/Moore models where we can have outputs associated with each state.

    So my question is, could you not have an output associated with the first state such that every time it would see a 0, an output signal would be generated to increment some external counter, so that when the machine finally does see a 1, it jumps to the next state and uses that counter information to know how many 1's to repeat?

    I'm guessing I am jumping ahead and adding more power to the 5-tuple description of what a FSA really is?
  2. jcsd
  3. Oct 11, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper

    What do you do when the counter overflows? Your idea works up to the maximum number the counter can hold, but it doesn't solve the problem for ANY value of n.

    You could easily make a counter big enough for any practical purpose (e.g. it would work if the number of 0s and 1s was as big as the number of atoms in the observable universe) but the question is about the theoretical situation when there is no limit to the size of n.
  4. Oct 11, 2012 #3
    Ahh that's right. I just over thought it and forgot that the counter itself would have to go to infinity. Thanks.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook