1
$\begingroup$

Is it possible to count in Automata theory?

I am begginer in Automata theory and I am trying to do some examples.

Currently I am working on a program that will recognise equal numbers of 0 and 1, but they are orderd in such manner that they are together, example: $$ 000111\rightarrow true \quad 0001111\rightarrow false \quad 00011 \rightarrow false \quad 010101\rightarrow false \quad $$ I am trying to figure out is there any possibility to count in Automation theory. If not can you please advise me how it would be possible to solve this assingment, because the only way for me is counting.

Thanks.

| cite | improve this question | |
$\endgroup$
  • 3
    $\begingroup$ Wait until you learn about the pumping lemma (or better, Myhill-Nerode). $\endgroup$ – Yuval Filmus Oct 8 '13 at 17:39
  • 1
    $\begingroup$ Yuval's hint is probably the best, though I can give you a very related alternative: A finite automaton can only have a finite and predetermined amount of memory that does not grow with the size of the input. Use this realization to determine if you can count. $\endgroup$ – mdxn Oct 8 '13 at 17:45
  • 2
    $\begingroup$ possible duplicate of Can an FSA count? $\endgroup$ – mdxn Oct 8 '13 at 17:45
5
$\begingroup$

Well, it depends of the kind of automata you are using. Roughly speaking, finite automata can only count modulo $d$ for some fixed $d$: for instance, you can test whether a word contains an odd number of $0$ or whether its length is a multiple of $5$. For your problem, finite automata will not suffice and you need a more powerful model of automata, for instance a pushdown automaton.

| cite | improve this answer | |
$\endgroup$

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.