patternMinor
Can an FSA count?
Viewed 0 times
countcanfsa
Problem
This may be a silly question. It seem clear that an FSA, since it is finite, can only count the number of symbols in its input string up to a number bounded by the number of its states. But now suppose we equip the FSA with output (e.g. printing) capabilities. It would then be very easy to construct a machine capable of printing one symbol for each symbol that it reads. Would that count as counting? If not, why not?
To put it in terms of FSTs instead: I take it that it is not possible to construct an FST capable of mapping a string of an arbitrary length to a binary representation (i.e. a number in the base-2 numeral system) of its length. But it IS of course trivial to construct an FST capable of mapping a string of arbitrary length to a string of says zeroes (or ones) of the same length. But that could count as counting, could it not, beacuse what the FST is doing is building a representation of the length of its input. A somewhat odd representation, but still a representation, is it not?
To put it in terms of FSTs instead: I take it that it is not possible to construct an FST capable of mapping a string of an arbitrary length to a binary representation (i.e. a number in the base-2 numeral system) of its length. But it IS of course trivial to construct an FST capable of mapping a string of arbitrary length to a string of says zeroes (or ones) of the same length. But that could count as counting, could it not, beacuse what the FST is doing is building a representation of the length of its input. A somewhat odd representation, but still a representation, is it not?
Solution
This question is a bit vague, so here is a vague answer:
Translating unary to unary is not exactly counting, since the machine doesn't actually "know" what the size of the input was "in the end".
You realize this, of course, which is why you question the fact that it is indeed counting.
Translating from unary to binary, however, seems like a way-more advanced operation, because it does not only involve counting, it also involves arithmetic.
So perhaps the more precise notion to look at, instead of counting, is comparing. That is, given two numbers (in unary) $1^n$ and $1^m$, determine if $n=m$.
The ability to do this comparison is what gives rise to the famous non-regular language $\{a^nb^n: n\ge 0\}$. And the inability of an NFA to count is what makes this language non-regular.
Interestingly, this language is a CFL. And indeed, the corresponding automata model - PDAs, do have the ability to do a limited comparison.
When you talk about comparing, transducers no longer give you any additional power, so the question is resolved in that sense.
An additional note: completely informally, the ability to compare two numbers can often be used to simulate a 2-counter machine Minsky Machine, which are equivalent to TMs.
Translating unary to unary is not exactly counting, since the machine doesn't actually "know" what the size of the input was "in the end".
You realize this, of course, which is why you question the fact that it is indeed counting.
Translating from unary to binary, however, seems like a way-more advanced operation, because it does not only involve counting, it also involves arithmetic.
So perhaps the more precise notion to look at, instead of counting, is comparing. That is, given two numbers (in unary) $1^n$ and $1^m$, determine if $n=m$.
The ability to do this comparison is what gives rise to the famous non-regular language $\{a^nb^n: n\ge 0\}$. And the inability of an NFA to count is what makes this language non-regular.
Interestingly, this language is a CFL. And indeed, the corresponding automata model - PDAs, do have the ability to do a limited comparison.
When you talk about comparing, transducers no longer give you any additional power, so the question is resolved in that sense.
An additional note: completely informally, the ability to compare two numbers can often be used to simulate a 2-counter machine Minsky Machine, which are equivalent to TMs.
Context
StackExchange Computer Science Q#11155, answer score: 9
Revisions (0)
No revisions yet.