Если нет, то что это значит, когда для некоторого состояния и некоторого символа , не существует?δ ( q , a )
12
Если нет, то что это значит, когда для некоторого состояния и некоторого символа , не существует?δ ( q , a )
Ответы:
Вы, кажется, наткнулись на спорный вопрос. Видимо, ученые-компьютерщики любят спорить. Я, конечно, люблю спорить, так что здесь идет!
Мой ответ однозначен: нет. Детерминированные конечные автоматы не нуждаются в переходе из каждого состояния для каждого символа. Смысл в том, что не существует, просто означает, что DFA не принимает входную строку.δ(q,a)
Хотя вы можете создать определение DFA, которое требует, чтобы существовал, просто не тот случай, когда пропущенный переход делает результирующую структуру (как бы вы ее ни называли) каким-либо образом недетерминированной, как многие комментаторы утверждают. Если вы проходите курс по теории автоматов, то следующей темой будут языки без контекста и автоматы с выпадающим меню, где различие между недетерминированными и детерминированными автоматами является критическим, и вам нужно использовать правильное определение недетерминизма.δ(q,a)
Недетерминизм связан с наличием более одного правового перехода.
Я думаю, что мы все согласны со следующим определением Википедии (которое я покажу через секунду, немного двусмысленно):
Детерминированный конечный автомат является 5-кортежем ( , , , , ), состоящим изM Q Σ δ q0 F
Пусть - строка над алфавитом . Автомат принимает строку если в существует последовательность состояний со следующими условиями:w=a1a2⋯an Σ M w r0,r1,…,rn Q
Неоднозначность и противоречие связаны с определением функции перехода, (число «3» в первом маркированном списке.) Мы все согласны с тем, что отличие DFA от NFA заключается в том, что является функцией, а не отношение . Но частичная функция или полная функция ?δ δ δδ δ
Определение DFA прекрасно работает, если является частичной функцией. При заданной входной строке, если вы достигнете состояния с входным символом где следующего состояния нет, автомат просто не примет.δ qi aj
Более того, когда вы расширяете это определение для создания определения автоматов с опрокидыванием, вы должны будете различать, что автоматы с опусканием с переходными функциями, которые являются частичными функциями, классифицируются как детерминированные, а не недетерминированные.
Если частичная функция вас беспокоит, то здесь есть тривиальное преобразование, которое делает полной функцией. (Это преобразование не похоже на алгоритм построения подмножества, оно добавляет не более O (1) состояний, является линейным по исходному числу состояний и может быть расширено для работы с КПК. Ни один из этих фактов не относится к алгоритму построения подмножества .)δ
У этого автомата есть , являющаяся общей функцией, которая принимает и отклоняет точно такой же набор состояний, что ваш исходный автомат принял и отклонил.δ
Редакция, январь 2019 г.
Комментатор @Alex Smart справедливо критикует меня за то, что я не даю ссылок и не объясняю, почему мы должны заботиться. Итак, здесь идет:
Причина, по которой мы заботимся о точном определении детерминизма по сравнению с недетерминизмом, заключается в том, что некоторые классы недетерминированных автоматов более мощные, чем их детерминированные кузены, а некоторые классы недетерминированных автоматов не более мощные, чем их детерминированные кузены. Для конечных автоматов и машин Тьюринга детерминированные и недетерминированные варианты имеют одинаковую степень. Для автоматов pushdown существуют языки, в которых важно это различие: есть NPDA, которые принимают язык, и ни один DPDA не принимает язык. Для линейных ограниченных автоматов вопрос является (или был проверен в последний раз) открытым. Увеличение мощности NPDA по сравнению с DPDA происходит благодаря разрешению нескольких переходы, а не от превращения функции перехода от полной функции к частичной функции.
Книги от сообщества компиляторов:
Ахо и Уллман, Принципы разработки компиляторов , 1977: сначала определяет NFA (стр. 88) с помощью отношения перехода, затем (стр. 90-91):
Aho, Sethi, и Ullman, составители, принципы, методы и инструменты , переиздание 1988 года, похожи, сначала они определяют NFA с переходным отношением, затем (стр. 115-116):
(Обратите внимание, что в комментариях @Alex Smart говорится: «Дракон особо упоминает, что функция является полной». Я предполагаю, что он говорит о более позднем издании с соавтором Лэмом, к которому у меня нет доступа в данный момент. )
Аппель, Современная реализация компилятора в Java , 1988 (стр. 22):
Далее Аппель объясняет, что при использовании DFA для распознавания самых длинных совпадений мы явно используем отсутствующие переходы, чтобы решить, когда остановиться (стр. 23):
Книги от сообщества теории переключения:
Кохави, Теория коммутации и конечных автоматов, 2 / е , 1978, с. 611 говорит:
Как правило, я бы однозначно истолковал значение «ровно один», а не «не более одного». (То есть, кажется, Кохави говорит, что детерминизм требует полной функции)
Книги из сообщества теоретиков вычислений:
Здесь представляется более распространенным определить DFA перед NFA и требовать, чтобы DFA имели общую функцию перехода, но затем определить NPDA перед DPDA и определить «детерминизм» как ограничение отношения перехода к наличию не более чем одна запись для каждой пары состояние / символ.
Это справедливо в отношении Хопкрофта и Уллмана, 1979 г., Льюиса и Пападимитриу, 1981 г., и, особенно, Сипсера, 2006 г., который педагогически использует определение DFA для точного формального определения, объясняет их важность и прямо говорит (с.36):
Интересно, что Рабин и Скотт также определяют недетерминированные конечные автоматы в терминах полной функции! Страница 120, определение 9:
То есть: общая функция перехода не делает систему детерминированной!
Sipser 2006 следует за Рабином и Скоттом и использует полную функцию перехода от состояний / символов к степенному набору состояний для своих определений недетерминированных конечных автоматов, недетерминированных КПК и недетерминированных машин Тьюринга, но пропускает тему детерминированных PDA.
И Хопкрофт, и Уллман, 1979, и Льюис и Пападимитриу, 1981, используют частичные функции в своих определениях детерминированных КПК. Сначала они определяют NPDA с переходным отношением, а затем, когда они попадают в КПК, Льюис и Пападимитриу говорят (с. 135),
В то время как Хопкрофт и Ульман говорят (с. 112):
источник
С точки зрения вычислимости NFA эквивалентны DFA - есть алгоритм для преобразования из NFA в DFA, а DFA - это просто NFA, который не использует недетерминированность, поэтому они оба определяют набор регулярных языков.
источник
Есть определения DFA в соответствии с
В этом случае вам не нужны все переходы. Если автомат не имеет переход фитинг следующий входной символ, он отвергает.
Это хорошее упражнение, чтобы показать, что оба определения эквивалентны с точки зрения того, какие языки могут быть приняты.
источник
В определении DFA, каждый штат должен иметь весь алфавит в £. Для примера, если £ = {а, b, c} и Q = {q0, q1, q2}, все это государства должны иметь все это, б, в символы, что переход на другое состояние или же состояние.
источник
Самый простой ответ на это, вы добавляете мертвое состояние для левого символа . Как и при преобразовании из NFA в DFA, мы получаем Φ переход для некоторых символов, что означает, что мы создаем для него мертвое состояние.
источник