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.

$\endgroup$
3
  • 3
    $\begingroup$ Wait until you learn about the pumping lemma (or better, Myhill-Nerode). $\endgroup$ Oct 8, 2013 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, 2013 at 17:45
  • 2
    $\begingroup$ possible duplicate of Can an FSA count? $\endgroup$
    – mdxn
    Oct 8, 2013 at 17:45

1 Answer 1

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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