Question about Finite State Automatons

[Wallboy]

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: {0ⁿ1ⁿ | 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?

 

[AlephZero]

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?

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.

 

[Wallboy]

Ahh that's right. I just over thought it and forgot that the counter itself would have to go to infinity. Thanks.