11
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ So you are really asking the question "what is counting?" That does not sound like computer science to me. It would be computer science if your question was "for this definition of counting, can an FSA count?". $\endgroup$ – Sasho Nikolov Apr 9 '13 at 17:19
8
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

No. Finite state automata do not count. They may do things that look like it, but they cannot count. They can even do a little (hard-wired) computations (like determining whether a binary number is divisible by three) but that is not counting.

A little story. You are on a big rectangular square in a famous city. The locals tell you the square is actually square. If you can count you check whether the horizontal and vertical numbers of tiles match by counting tiles along the sides of the square. If you cannot count you can still verify the claim: start at a corner and walk diagonally. If you exactly reach the opposite corner you have a square.

In your example the fsa tests whether a string has an equal number of $a$'s and $b$'s by tallying these numbers to two different output tapes. Another device has to be doing the final comparison, unless you have a trick to handle the letters $a$ and $b$ in pairs and cros off one against the other. Like in the square.

Now a more formal model to compare with. According to the Chomsky–Schützenberger Theorem every context-free language $L$ is an inverse of a finite state transduction $T$ of the Dyck language $D_2$ on two pairs of brackets $L = T^{-1}(D_2)$ (it is not stated like that on wikipedia, but you have to believe me). Now the finite state transducer $T$ can "accept" its context-free language $L$ as follows (for each language its own transducer). On input $T$ transforms the string into the (guessed) series of pops and pushes of the pda for $L$, then test whether the result is pushdown behaviour, i.e., the result is a string in $D_2$. (Technical details omitted, but this is as claimed by the Ch-Sch Theorem: one has $w\in T^{-1}(D_2)$ iff $T(w) \in D_2$)

My point here is that some "computation" is done by the transducer but much power is hidden in the test with $D_2$. Likewise your example, where two letters are sorted on two tapes.

$\endgroup$
  • $\begingroup$ I can construct a DFA that counts between $0$ to $2^{n!}$ (for fixed $n$) or even in $\mathbb{N}$. That's more than any human or real computer manages. What would you call counting? $\endgroup$ – Raphael Apr 10 '13 at 8:53
  • $\begingroup$ @Raphael. Sure. And easily larger numbers than that. Stop teaching that context-free languages are more powerful than regular languages: they are the same (at least for strings of length at most $2^{n!}$). Just joking. Referring to real computer languages like that makes anything finite state isn't it? Finite state automata do not count! They just distinguish a finite number of states, although that number may be very large. $\endgroup$ – Hendrik Jan Apr 10 '13 at 9:39
  • $\begingroup$ But the way FSAs are usually presented, they are only "allowed" to say either "yes" (accepted) or "no" (not accepted). Given this, no one could construct an FSA that counts. If we allow it to report (e.g. print) the (number of the) state it is in when it terminates, then it can count, but only up to a bound given by the number of states. But if DO we allow it to print, then it is trivial to construct a single state FSA that prints (say) 1 each time it reads a symbol from the input string, thus reporting the count in the tally representation. What's wrong with this idea? $\endgroup$ – Torbjörn Apr 10 '13 at 10:06
  • $\begingroup$ And if we forget about reporting/printing, and think in terms of internal representations instead, an FSA can count the symbols in a string, but not in an arbitrary long one. The single state FSA then of course cannot count at all. $\endgroup$ – Torbjörn Apr 10 '13 at 10:44
  • $\begingroup$ Hendrik, I think we are "debating" a matter of semantics: for me, "counting" can be "from one to ten" which FA can do. When intersecting Büchi-automata, for instance, we count how many (of $k$, fixed) automata have reached a final state while the others proceed. Therefore, I think the statement "can not count" is too strong. The (only) true statement is "the can not count farther than to a constant". $\endgroup$ – Raphael Apr 10 '13 at 11:10
1
$\begingroup$

@Shaull: Thanks for your answer! I'm new to StackExchange and don't know how to comment on an answer, so I choose to write an answer instead, in the hope that I may be forgiven.

Hmm, it seems to me that a shepard counting his sheep by writing a mark on a slip of paper for each sheep that he sees, or a prisoner counting the days he's been in jail by writing marks on the wall, are counting. Why wouldn't n marks on a slip of paper or on a wall count as a representation of the number n? Isn't that what is called a tally representation? AFAICS it is in no obvious way inferior to (say) a binary representation, except that it uses more space.

I suppose that for you then, "know" means that it has an internal representation of the count in the end. Then, of course, it is obvious that an FSA of FST cannot compute the length of an arbitrary string. But if we don't require knowledge in that sense, but demand only that the FSA or FST should be able to tell the result to an external observer, then it seems to me that presenting the count in a tally format should be ok.

Furthermore, if an FSA is equipped with both incremental input and output, then it should in principle be able to use its external environment as a read/write memory, and thus be as powerful as a Turing machine. Right?

Thanks for bringing up the case of comparing. Now, it appears to be the case that if we lift the requirement of an internal representation, and we only require that the machine is able to present the result to en external observer, then we could easily build an FSM that could produce a kind of graphical presentation of the outcome. Suppose the FSM, upon readins "aaaaaabbbbbb" wrote

000000
000000

then, since the bars are of the same length, the FSM has accepted the string "aaaaaabbbbbb". Two bars of the same length means "yes", different lengths means "no".

I guess I'm bending the rules, but that's what I want since I'm interested in the more or less implicit assumptions that are being made in the field of mathematical linguistics.

$\endgroup$
  • $\begingroup$ Perhaps your "model" can be seen as a FSA with a finite number (equal to the alphabet size) of write only counters plus a special final state that can compare two (or more) of them and accept or reject according if they are equal or not. Such "$FSA_{WOC}$" is more powerful than a FSA; but it has some troubles recognizing things like $\{a^n | n \mbox{ is prime }\}$ i.e. doing arithmetic. $\endgroup$ – Vor Apr 9 '13 at 13:53
  • $\begingroup$ I think the difference between the examples you give and FST-output is that the shepherd can read the lines after they are written, whereas an FSM can't. Same goes for comparing. $\endgroup$ – Shaull Apr 9 '13 at 18:49
  • $\begingroup$ You can comment by clicking the "add comment" link beneath any post. $\endgroup$ – Raphael Apr 10 '13 at 8:55
  • $\begingroup$ Any FSA constructed to count a flock can count that flock. No constructed FSA can count any flock. The basic question is whether the shepherd only knows how to count far enough to at least count his own flock, or can use the full range of the natural numbers. In my experience, we humans must explicitly make the transition between the two capabilities at some point in our mathematics education. $\endgroup$ – reinierpost Apr 11 '13 at 8:37
1
$\begingroup$

FSMs can "count" within a finite range/number of steps signified by state transitions. however, they cannot count past a finite number of steps.

there is a sense in which an FSA-like machine can count. a closely related machine is called a Finite State Transducer. the transducer can indeed count in the sense of "piped" input and output. a single transducer can take an input sequence (say in binary) and "transduce" it to an output sequence that is incremented. then one "chains" the (identical) count-by-1 transducers, each one incrementing its input by 1 and outputting it. its also like a rudimentary "streaming algorithm".

$\endgroup$
  • $\begingroup$ more detail: the transducer can increment working in "lsb" to "msb" order ie "least sig bit" to "most sig bit" using logic similar to the EE full adder. $\endgroup$ – vzn Apr 9 '13 at 20:48
  • $\begingroup$ fyi finite state transducers seem not to have been studied a whole lot. there is another interesting application to the collatz conjecture in creating a machine that calculates iterates. anyone interested in further theory/discussion plz contact me in chat or on my blog. $\endgroup$ – vzn Apr 11 '13 at 3:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.