В DFA каждый штат имеет переход по каждому символу алфавита?

12

Если нет, то что это значит, когда для некоторого состояния и некоторого символа , не существует?qδ ( q , a )aδ(q,a)

Дункан
источник
Я бы назвал недетерминированный автомат, который никогда не имеет более одного перехода в одном состоянии и входной символ детерминирован. Это просто не соответствует определению DFA.
сообщение от
1
Если правила DFA расположены так, что он никогда не может находиться в состоянии q, когда символ на ленте - это a , нужно ли нам действительно определять δ (q, a) ?
Питер Шор
4
Ответ очевиден: это зависит от того, как определяется «детерминированный конечный автомат». Таким образом, я не уверен, что этот вопрос является полностью конструктивным, поскольку нет общепринятого правильного ответа - то есть этот вопрос требует мнения и дебатов.
Patrick87
1
Если предполагается, что является функцией , она должна быть определена для всех пар . q , aδq,a
vonbrand
В моем представлении о DFA, это условие «прервать», или если вы предпочитаете неявный переход в состояние «отклонить».
Ив Дауст

Ответы:

22

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

Мой ответ однозначен: нет. Детерминированные конечные автоматы не нуждаются в переходе из каждого состояния для каждого символа. Смысл в том, что не существует, просто означает, что DFA не принимает входную строку.δ(q,a)

Хотя вы можете создать определение DFA, которое требует, чтобы существовал, просто не тот случай, когда пропущенный переход делает результирующую структуру (как бы вы ее ни называли) каким-либо образом недетерминированной, как многие комментаторы утверждают. Если вы проходите курс по теории автоматов, то следующей темой будут языки без контекста и автоматы с выпадающим меню, где различие между недетерминированными и детерминированными автоматами является критическим, и вам нужно использовать правильное определение недетерминизма.δ(q,a)

Недетерминизм связан с наличием более одного правового перехода.

Я думаю, что мы все согласны со следующим определением Википедии (которое я покажу через секунду, немного двусмысленно):

Детерминированный конечный автомат является 5-кортежем ( , , , , ), состоящим изMQΣδq0F

  1. конечное множество состояний ( )Q
  2. конечный набор входных символов, называемых алфавитом ( )Σ
  3. функция перехода ( )δ:Q×ΣQ
  4. начальное состояние (q0Q)
  5. набор принимающих состояний ( ).FQ

Пусть - строка над алфавитом . Автомат принимает строку если в существует последовательность состояний со следующими условиями:w=a1a2anΣMwr0,r1,,rnQ

  1. r0=q0
  2. ri+1=δ(ri,ai+1) , дляi=0,,n1
  3. rnF .

Неоднозначность и противоречие связаны с определением функции перехода, (число «3» в первом маркированном списке.) Мы все согласны с тем, что отличие DFA от NFA заключается в том, что является функцией, а не отношение . Но частичная функция или полная функция ?δδ δδδ

Определение DFA прекрасно работает, если является частичной функцией. При заданной входной строке, если вы достигнете состояния с входным символом где следующего состояния нет, автомат просто не примет.δqiaj

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

Если частичная функция вас беспокоит, то здесь есть тривиальное преобразование, которое делает полной функцией. (Это преобразование не похоже на алгоритм построения подмножества, оно добавляет не более O (1) состояний, является линейным по исходному числу состояний и может быть расширено для работы с КПК. Ни один из этих фактов не относится к алгоритму построения подмножества .)δ

  1. добавить состояниеqerror
  2. для каждой пары где не определена, определите .(qi,sj)δδ(qi,sj)=qerror

У этого автомата есть , являющаяся общей функцией, которая принимает и отклоняет точно такой же набор состояний, что ваш исходный автомат принял и отклонил.δ

Редакция, январь 2019 г.

Комментатор @Alex Smart справедливо критикует меня за то, что я не даю ссылок и не объясняю, почему мы должны заботиться. Итак, здесь идет:

Причина, по которой мы заботимся о точном определении детерминизма по сравнению с недетерминизмом, заключается в том, что некоторые классы недетерминированных автоматов более мощные, чем их детерминированные кузены, а некоторые классы недетерминированных автоматов не более мощные, чем их детерминированные кузены. Для конечных автоматов и машин Тьюринга детерминированные и недетерминированные варианты имеют одинаковую степень. Для автоматов pushdown существуют языки, в которых важно это различие: есть NPDA, которые принимают язык, и ни один DPDA не принимает язык. Для линейных ограниченных автоматов вопрос является (или был проверен в последний раз) открытым. Увеличение мощности NPDA по сравнению с DPDA происходит благодаря разрешению нескольких переходы, а не от превращения функции перехода от полной функции к частичной функции.

Книги от сообщества компиляторов:

Ахо и Уллман, Принципы разработки компиляторов , 1977: сначала определяет NFA (стр. 88) с помощью отношения перехода, затем (стр. 90-91):

Мы говорим, что конечный автомат является детерминированным, если 1. Он не имеет переходов на входе . 2. Для каждого состояния и входного символа существует не более одного ребра, помеченного выходящий .ϵssaas

Aho, Sethi, и Ullman, составители, принципы, методы и инструменты , переиздание 1988 года, похожи, сначала они определяют NFA с переходным отношением, затем (стр. 115-116):

Детерминированные конечные автоматы (DFA, для краткости) представляет собой частный случай недетерминистическую finitie автомата , в котором ... есть более одного ребра помечена оставляя .as

(Обратите внимание, что в комментариях @Alex Smart говорится: «Дракон особо упоминает, что функция является полной». Я предполагаю, что он говорит о более позднем издании с соавтором Лэмом, к которому у меня нет доступа в данный момент. )

Аппель, Современная реализация компилятора в Java , 1988 (стр. 22):

В детерминированном конечном автомате (DFA) никакие два ребра, выходящие из одного и того же состояния, не помечены одинаковым символом.

Далее Аппель объясняет, что при использовании DFA для распознавания самых длинных совпадений мы явно используем отсутствующие переходы, чтобы решить, когда остановиться (стр. 23):

когда достигается мертвое состояние (не конечное состояние без выходных переходов), переменные [которые записывают самое длинное совпадение, которое мы видели до сих пор], сообщают, какой токен был найден и где он закончился.

Книги от сообщества теории переключения:

Кохави, Теория коммутации и конечных автоматов, 2 / е , 1978, с. 611 говорит:

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

Как правило, я бы однозначно истолковал значение «ровно один», а не «не более одного». (То есть, кажется, Кохави говорит, что детерминизм требует полной функции)

Книги из сообщества теоретиков вычислений:

Здесь представляется более распространенным определить DFA перед NFA и требовать, чтобы DFA имели общую функцию перехода, но затем определить NPDA перед DPDA и определить «детерминизм» как ограничение отношения перехода к наличию не более чем одна запись для каждой пары состояние / символ.

Это справедливо в отношении Хопкрофта и Уллмана, 1979 г., Льюиса и Пападимитриу, 1981 г., и, особенно, Сипсера, 2006 г., который педагогически использует определение DFA для точного формального определения, объясняет их важность и прямо говорит (с.36):

δ

s×Σ

Интересно, что Рабин и Скотт также определяют недетерминированные конечные автоматы в терминах полной функции! Страница 120, определение 9:

MS×ΣS

То есть: общая функция перехода не делает систему детерминированной!

Sipser 2006 следует за Рабином и Скоттом и использует полную функцию перехода от состояний / символов к степенному набору состояний для своих определений недетерминированных конечных автоматов, недетерминированных КПК и недетерминированных машин Тьюринга, но пропускает тему детерминированных PDA.

И Хопкрофт, и Уллман, 1979, и Льюис и Пападимитриу, 1981, используют частичные функции в своих определениях детерминированных КПК. Сначала они определяют NPDA с переходным отношением, а затем, когда они попадают в КПК, Льюис и Пападимитриу говорят (с. 135),

Интуитивно понятный автомат с нажатием кнопки является детерминированным , если к каждой конфигурации применимо не более одного перехода.

В то время как Хопкрофт и Ульман говорят (с. 112):

КПК ... является детерминированным в том смысле, что с любого идентификатора возможен максимум один ход.

Блуждающая логика
источник
qerror
2
Частичная версия функции - это та, что приведена в Хопкрофте и Уллмане, если это имеет значение. Таким образом, идея о том, что частичная функция по своей природе недетерминирована, ни в коем случае не является стандартной.
13
1
@jmite Дело не в том, что частичные функции подразумевают недетерминизм; именно тотальные функции подразумевают детерминизм, что делает тотальные функции лучшим выбором. Конечно, это более или менее произвольный вопрос о определениях, которые вы используете.
Patrick87
3
δ
1
Как вы показали, версия с частичной функцией имеет легкий перевод на полную версию функции, и, насколько я вижу, вы абсолютно ничего не получаете, педагогически или иным образом, позволяя функции перевода быть частичной. Дракон особо упоминает, что функция полная. Почему в мире мы приводим аргумент о чем-то, что было четко определено в стандартном учебнике, которому следует большинство людей, когда абсолютно ничего не выиграет от выбора нестандартного определения?
Алекс Смарт
8

δ(q,a)qQaΣQΣ

ε

С точки зрения вычислимости NFA эквивалентны DFA - есть алгоритм для преобразования из NFA в DFA, а DFA - это просто NFA, который не использует недетерминированность, поэтому они оба определяют набор регулярных языков.

Люк Мэтисон
источник
2
Это зависит от определения; Есть несколько, которые эквивалентны по силе.
Рафаэль
3
+1 Лучше всего придерживаться этого определения, ИМХО, поскольку все согласятся, что FA, который определяет ровно один переход для каждой пары (состояние, символ), представляет собой действительный DFA.
Patrick87
1
И это определение совершенно неверно, когда вы пытаетесь расширить его, чтобы решить, является ли контекстно-свободный язык детерминированным или недетерминированным. Автоматы с отсутствующими переходами всегда могут быть преобразованы в автомат с одним переходом на состояние / входной символ / символ стека. Недетерминированные автоматы нажатия с несколькими возможными переходами на состояние / входной символ / символ стека не обязательно могут быть преобразованы в детерминированные автоматы нажатия. (Например: в случае, если распознанный язык является недетерминированным контекстно-свободным.)
Блуждающая логика
2
@jmite Просто определите обрезные автоматы независимо от DFA. Я думаю, что гораздо важнее, чтобы минимальные DFA имели правильное количество состояний в соответствии с теоремой Майхилла-Нерода, которую вы получаете только с мертвыми состояниями.
Patrick87
4
ϵϵϵ
6

Есть определения DFA в соответствии с

A|δ(q,a)|1qaδ(q,ε)δ(q,a)=aΣA

В этом случае вам не нужны все переходы. Если автомат не имеет переход фитинг следующий входной символ, он отвергает.

Это хорошее упражнение, чтобы показать, что оба определения эквивалентны с точки зрения того, какие языки могут быть приняты.

Рафаэль
источник
Я думаю, что вопрос OP должен быть отредактирован, чтобы включить формальное определение DFA.
scaaahu
0

В определении DFA, каждый штат должен иметь весь алфавит в £. Для примера, если £ = {а, b, c} и Q = {q0, q1, q2}, все это государства должны иметь все это, б, в символы, что переход на другое состояние или же состояние.

Хаси Амаратунга
источник
1
Какая разница из существующих ответов , так что вы размещаете новый ответ?
xskxzr
0

Самый простой ответ на это, вы добавляете мертвое состояние для левого символа . Как и при преобразовании из NFA в DFA, мы получаем Φ переход для некоторых символов, что означает, что мы создаем для него мертвое состояние.

НИКС
источник