Разрешимость трех государственных FA

Question

Я пытаюсь выяснить, как описать пятьдесят шесть строк, чтобы проверить, имеет ли FA из трех состояний над алфавитом {a b} конечный язык.

Число пятьдесят шесть происходит из теоремы, которая гласит, что если машина имеет N состояний, а алфавит состоит из m букв, то в общей сложности m^N + m^(N + 1) + m^(N + 2) +...+ m^(2N-1) разные входные строки в диапазоне N<= длина строки < 2N. Таким образом, 2^3 2^4 2^5 = 56 строк.

Я знаю, что мы можем проверить их все, запустив их на компьютере, и если они будут приняты, язык будет бесконечным, если ни один не принят, язык конечен.

Я просто не знаю, как описать строки. Любая помощь очень ценится!

Answer 1

В случае, если кто-либо когда-либо сталкивался с одним и тем же вопросом, были связаны с N до 2N - 1.

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