Обычный язык не принят DFA, имеющий не более трех штатов

10

Опишите обычный язык, который не может быть принят ни одним DFA, имеющим только три состояния.

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

zic10
источник

Ответы:

17

Можно утверждать, что лемма прокачки учитывает число состояний в DFA. Каждый язык принятый DFA с p- состояниями, удовлетворяет следующей лемме прокачки:Lп

Каждое слово длиной не менее p можно разбить на w = x y z , где | х у | p и | у | 1 , такое, что x y i z L для всех i 0 .wpw=xyz|xy|p|y|1xyizLi0

Вы можете использовать эту характеристику, чтобы доказать, что язык требует p + 1 состояний.{0p}p+1

Другой метод заключается в использовании теоремы Майхилла - Нерода. Два слова являются неэквивалентных (относительно некоторого языка L ) , если для некоторого слова г , либо х г L и у г L или наоборот. Теорема Майхилла - Нерода утверждает, что если существует p попарно неэквивалентных слов, то каждый DFA для L имеет не менее p состояний. Для примера L = { 0 p } вы можете найти p + 1x,YLZxzLyzLпLпL={0p}п+1попарно неэквивалентные слова, а именно .ε,0,...,0п

Юваль Фильмус
источник
Да, zможет быть ^пустым, но я думаю, что в вашей цитате есть опечатка. xy^i ∈ L должно бытьxy^i z ∈ L
Grijesh Chauhan
12

Ответ Ювала великолепен. Более простая формулировка того, что он описал, состоит в том, что конечные автоматы не могут считать произвольно высокое число, и количество, на которое они могут рассчитывать, ограничено числом состояний в автоматах. Точнее, для того, чтобы автомат считал до , ему нужно состояние p + 1 (одно состояние будет 0 ).пп+10

По сути, в этом и заключается вся идея леммы прокачки: если строка действительно длинная, конечные автоматы должны «забыть», как высоко она считается, и начинать все заново, что позволяет вам повторять раздел снова и снова, не заботясь о нем. ,

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

Вы можете думать о таком языке? (Ваш профессор может также ожидать, что вы докажете этот счетный аргумент, хотя в моем учебном плане это понимание леммы прокачки было воспринято как должное)

Алексис Бессесснер
источник
Хороший ответ: он многое объясняет, не давая решения тому, что похоже на домашнее задание. Добро пожаловать в информатику !
Дэвид Ричерби
1

Существует алгоритм для минимизации DFA. Просто выберите язык с минимальным DFA из 4 (или более) состояний. Подойдет все, что имеет минимальную длину 3 символа, т. Е. Язык регулярного выражения или (еще проще) a 3 . Чтобы понять почему, взгляните на доказательство леммы прокачки для обычных языков.a3a*a3

vonbrand
источник
-2

другая идея, диагонализация ! Перечислите все DFA с тремя или меньшим количеством штатов, возьмите объединение всех из них, а затем возьмите дополнение. это DFA путем закрытия регулярных языковых операций. это можно построить с помощью алгоритма, но вопрос требует только описания .

ВЗН
источник
N
NN+1
@ Юваль верно. думаю, что эта идея может сработать, но, возможно, детали не совсем
точны, детали хитры,