Можно утверждать, что лемма прокачки учитывает число состояний в DFA. Каждый язык принятый DFA с p- состояниями, удовлетворяет следующей лемме прокачки:Lп
Каждое слово длиной не менее p можно разбить на w = x y z , где | х у | ≤ p и | у | ≥ 1 , такое, что x y i z ∈ L для всех i ≥ 0 .веспш = х уZ| ху| ≤р| Y| ≥1х уяZ∈ Lя ≥ 0
Вы можете использовать эту характеристику, чтобы доказать, что язык требует p + 1 состояний.{ 0п}р + 1
Другой метод заключается в использовании теоремы Майхилла - Нерода. Два слова являются неэквивалентных (относительно некоторого языка L ) , если для некоторого слова г , либо х г ∈ L и у г ∉ L или наоборот. Теорема Майхилла - Нерода утверждает, что если существует p попарно неэквивалентных слов, то каждый DFA для L имеет не менее p состояний. Для примера L = { 0 p } вы можете найти p + 1х , уLZх з∈ LYZ∉ LпLпL = { 0п}р + 1попарно неэквивалентные слова, а именно .ϵ , 0 , … , 0п
z
может быть^
пустым, но я думаю, что в вашей цитате есть опечатка.xy^i ∈ L
должно бытьxy^i z ∈ L
Ответ Ювала великолепен. Более простая формулировка того, что он описал, состоит в том, что конечные автоматы не могут считать произвольно высокое число, и количество, на которое они могут рассчитывать, ограничено числом состояний в автоматах. Точнее, для того, чтобы автомат считал до , ему нужно состояние p + 1 (одно состояние будет 0 ).п р + 1 0
По сути, в этом и заключается вся идея леммы прокачки: если строка действительно длинная, конечные автоматы должны «забыть», как высоко она считается, и начинать все заново, что позволяет вам повторять раздел снова и снова, не заботясь о нем. ,
Следовательно, любой обычный язык, требующий подсчета до 3 для проверки слова в нем, не может быть описан конечными автоматами размера 3.
Вы можете думать о таком языке? (Ваш профессор может также ожидать, что вы докажете этот счетный аргумент, хотя в моем учебном плане это понимание леммы прокачки было воспринято как должное)
источник
Существует алгоритм для минимизации DFA. Просто выберите язык с минимальным DFA из 4 (или более) состояний. Подойдет все, что имеет минимальную длину 3 символа, т. Е. Язык регулярного выражения или (еще проще) a 3 . Чтобы понять почему, взгляните на доказательство леммы прокачки для обычных языков.a3a* a3
источник
другая идея, диагонализация ! Перечислите все DFA с тремя или меньшим количеством штатов, возьмите объединение всех из них, а затем возьмите дополнение. это DFA путем закрытия регулярных языковых операций. это можно построить с помощью алгоритма, но вопрос требует только описания .
источник