Давайте рассмотрим несколько строк на языке:
12 = 1*3 + 2 = 5 ~ 5 (mod 6)
102 = 1*9 + 0*3 + 2 = 11 ~ 5 (mod 6)
122 = 1*9 + 2*3 + 2 = 17 ~ 5 (mod 6)
212 = 2*9 + 1*3 + 2 = 23 ~ 5 (mod 6)
1002 = 1 * 18 + 0 * 9 + 0 * 9 + 2 = 29 ~ 5 (мод 6)
Мы замечаем, что все строки заканчиваются на 2. Это имеет смысл, поскольку 6 кратно 3, и единственный способ получить 5 из кратного 3 - это добавить 2. На основании этого мы можем попытаться решить проблему строки, совпадающие с 3 по модулю 6:
10 = 3
100 = 9
120 = 15
210 = 21
1000 = 27
Реального шаблона не возникает, но учтите это: каждое число в base-3, оканчивающееся на 0, определенно делится на 3. Те, которые четны, также делятся на 6; поэтому нечетные числа, чье представление base-3 оканчивается на 0, должны быть согласованы с 3 mod 6. Поскольку все степени 3 нечетные, мы знаем, что у нас есть нечетное число, если число 1 в строке нечетное.
Итак, наши условия:
- строка начинается с 1;
- строка имеет нечетное число 1 с;
- строка заканчивается 2;
- строка может содержать любое количество 2 и 0.
Чтобы получить минимальное количество состояний в таком DFA, мы можем использовать теорему Майхилла-Нерода, начинающуюся с пустая строка:
- за пустой строкой может следовать любая строка в языке. Назовите его класс эквивалентности [e]
- , за строкой 0 ничего не следует, поскольку допустимые представления base-3 не имеют ведущих нулей. Вызовите его класс эквивалентности [0].
- за строкой 1 следует символ, в котором есть четное число 1, заканчивающееся на 2. Вызовите его класс эквивалентности [1].
- за строкой 2 может следовать что угодно на языке. Действительно, вы можете проверить, что размещение 2 в начале любой строки в языке дает другую строку в языке. Однако за ним также могут следовать строки, начинающиеся с 0. Таким образом, его класс новый: [2].
- за строкой 00 не может следовать что-либо для ее исправления; его класс совпадает с его префиксом 0, [0]. то же самое для строки 01.
- за строкой 10 может следовать любая строка с четным числом 1, которая заканчивается на 2; поэтому он эквивалентен классу [1].
- за строкой 11 может следовать любая строка в языке; действительно, вы можете проверить, что добавление 11 перед любой строкой в языке дает другое решение. Однако за ним также могут следовать строки, начинающиеся с 0. Поэтому его класс такой же, как [2]. За
- 12 может следовать строка с четным числом 1, заканчивающимся на 2, а также как по пустой строке (так как 12 на самом деле на языке). Это новый класс, [12].
- 21 эквивалентен 1; класс [1]
- 22 эквивалентен 2; класс [2]
- 20 эквивалентен 2; класс [2]
- 120 неотличим от 1; его класс [1].
- 121 неотличим от [2].
- 122 неотличим от [12].
Мы не видели никакой новой эквивалентности занятия по новым строкам длины 3; Итак, мы знаем, что мы видели все классы эквивалентности. Они следующие:
- [e]: любая строка в языке может следовать за этим
- [0]: ни одна строка не может следовать за этим
- [1] : строка с четным числом 1, заканчивающаяся на 2, может следовать за этим
- [2]: то же самое, что и [e], но также строки, начинающиеся с 0
- [12]: то же, что [1 ] но также и пустая строка
Это означает, что минимальный DFA для нашего языка имеет пять состояний. Вот DFA:
[0]
^
|
0
|
----->[e]--2-->[2]<-\
| ^ |
| | |
1 __1__/ /
| / /
| | 1
V V |
[1]--2-->[12]
^ |
| |
\___0___/
(переходы, которые не изображены, являются самоконтролями в соответствующих состояниях).
Примечание: я ожидал, что этот DFA будет иметь 6 состояний, как указал Уэлбог в другой ответ, так что я мог пропустить класс эквивалентности. Тем не менее, DFA кажется сразу после проверки нескольких примеров и размышлений о том, что он делает: вы можете только принять состояние [12], увидев 2 как последний символ (безусловно, необходимый), и вы можете получить только состояние [12] из состояния [1], и вы, должно быть, видели нечетное число 1, чтобы добраться до [1]…