Я бы порекомендовал, чтобы в подобных случаях вы использовали теорему Майхилла-Нерода напрямую, либо чтобы найти число состояний в минимальном DFA для языка, либо чтобы обнаружить, что язык нерегулярен, потому что это требуется бесконечно много состояний.
Если вы никогда не слышали о теореме Майхилла-Нерода, вы могли бы вместо этого слышать об отношении неразличимости строк в отношении языка. Две строки x и y неразличимы по отношению к языку L, если для любой строки w такой, что xw находится в L, yw также находится в L, и наоборот. Строки, которые неразличимы, относятся к классам эквивалентности относительно отношения неразличимости, и эти классы непосредственно соответствуют состояниям минимального DFA для языка (если существует конечное число классов эквивалентности, то есть!).
To используя это, мы начинаем проверять строки в возрастающем лексикографическом порядке, пока не обнаружим, что для строк длины k мы не ввели новые классы эквивалентности по неразличимости (или мы распознаем некоторый шаблон, который говорит нам, что будет бесконечно много классов эквивалентности).
За пустой строкой может следовать любая строка в L, чтобы получить строку в L (тривиально). У нас всегда будет некоторый класс эквивалентности для пустой строки. Это равносильно тому, что любой DFA должен иметь хотя бы одно состояние - начальное состояние. Примечание: пустая строка на нашем языке, так как 0 - 0 = 0 (мод 3). Состояние, соответствующее этому классу эквивалентности, будет приниматься, если мы получим DFA. Вызовите класс эквивалентности и состояние [e].
За строкой a не может следовать ни одна строка в языке (1 - 0! = 0 (mod 3)), поэтому мы уже знать, что класс эквивалентности должен отличаться от [e]. Строки, которые могут следовать за этим, подобны тем, которые могут следовать за пустой строкой, за исключением того, что они должны удовлетворять #a(x) - #b(x) = 2 (mod 3).
За строкой b не может следовать ни одна строка в языке (0 - 1! = 0 (мод 3)), поэтому мы знаем, что это новый класс [b]. Фактически, строки, следующие за строкой b, должны удовлетворять #a(x) - #b(x) = 1 (mod 3), если они должны привести строку b к единице в языке.
За строкой aa не может следовать ни одна строка на языке (2 - 0! = 0 (мод 3)), поэтому мы знаем, что это не класс [e]. Однако мгновенное отражение покажет, что эта строка неотличима от строки b в том смысле, что любая строка, которая переводит строку aa в строку в языке, также переводит строку b в строку в языке, и наоборот , Рассмотрим: (aa) a, (aa) bb,…; против: (б) а, (б) бб,…. Поскольку aa неотличима от b, мы не добавляем для него новый класс или состояние эквивалентности.
Строка ab неотличима от пустой строки в том смысле, что можно добавить любую строку в L чтобы получить еще одну строку в L. Не нужно определять новый класс эквивалентности.
Строка ba неотличима от ab; опять же, новый класс эквивалентности не требуется.
Строка bb неотличима от строки a: (bb) b, (bb) aa,…; по сравнению с (a) b, (a) aa,…
При рассмотрении строк длины два нам не нужно было вводить какие-либо новые классы эквивалентности; это означает, что мы закончили и язык, который мы рассматриваем, является регулярным. Имеет состояния, соответствующие классам эквивалентности [e], [a] и [b]. Более того, мы можем получить переходы, посмотрев, какое состояние соответствует классу эквивалентности для конкатенации репрезентативной строки состояния (пусто, a или b) и символа в переходе.
Конкатенация a на пустую строку дает строку a, поэтому происходит переход по символу a с [e] на [a], поскольку a = ea;
Конкатенация b на пустую строку дает строку b, поэтому для символа b происходит переход от [e] к `[b], поскольку b = eb;
Конкатенация a на a дает строку aa, а aa неотличима от b; поэтому для символа a происходит переход от [a] к [b], поскольку aa = aa и aa ~ b;
Конкатенация b на a дает строку ab, а ab неотличим от пустой строки; поэтому для символа b происходит переход от [a] к [e], поскольку ab = ab и ab ~ e;
Конкатенация a на b дает строку ba, а ba неотличим от пустой строки; поэтому для символа a происходит переход от [b] к [e], поскольку ba = ba и ba ~ e;
Конкатенация b на b дает строку bb, а bb - неотличим от строки а; Итак, для символа b происходит переход от [b] к [a], поскольку bb = bb и bb ~ a.
Полученный DFA выглядит следующим образом:
b
/--------\
| |
| /--->[a]
V / a | ^
----->[e] a| |b
^ \ b V |
| \--->[b]
| |
\--------/
a