2
$\begingroup$

Im trying to figure out how to describe fifty-six strings to test if a three state FA over the alphabet $\{a,b\}$ has a finite language.

The number fifty-six comes from a theorem that states if a machine has $N$ states and an alphabet has $m$ letters, then in total there are $m^N + m^{N + 1} + m^{N + 2} +\ldots+ m^{2N-1}$ different input strings in the range $N \leq \text{length of string} < 2N$. Thus $2^3 2^4 2^5 = 56$ strings.

I know that we can test them all by running them on the machine and if any are accepted, the language is infinite, if none are accepted, the language is finite. I'm just not sure how to describe the strings.

Improve this question
$\endgroup$
2
  • $\begingroup$ The last statement "if any are accepted, the language is infinite" is somewhat surprising at first. For example, as a consequence, there does not exist a three state FA that only accepts the string '000'? $\endgroup$
    – Joe
    Commented Oct 8, 2012 at 23:27
  • $\begingroup$ At this point (revision 3) your question seems too general. $\endgroup$
    – Bartosz Przybylski
    Commented Dec 12, 2012 at 17:02

1 Answer 1

Reset to default
3
$\begingroup$

The strings are just all strings of lengths $N$ to $2N-1$. In your case:

000 001 010 011 100 101 110 111

0000 0001 0010 0011 0100 0101 0110 0111

1000 1001 1010 1011 1100 1101 1110 1111

00000 00001 00010 00011 00100 00101 00110 00111

01000 01001 01010 01011 01100 01101 01110 01111

10000 10001 10010 10011 10100 10101 10110 10111

11000 11001 11010 11011 11100 11101 11110 11111

Improve this answer
$\endgroup$
1
  • $\begingroup$ Oh ok, I see how you did it, thanks!!! $\endgroup$
    – user3115
    Commented Oct 8, 2012 at 23:48

Your Answer

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