Может ли DFA иметь переходы эпсилон/лямбда?

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


state-machine dfa finite-automata automata automata-theory
person liwing    schedule 09.12.2012    source источник
comment
Что вы подразумеваете под лямбда-переходом?   -  person Bhushan Firake    schedule 10.12.2012
comment
В некоторых книгах вместо эпсилон используется лямбда. Это то же самое.   -  person liwing    schedule 10.12.2012

Ответы (3)


arrow_upward
18
arrow_downward

DFA не имеет эпсилон-переходов. Если бы он был, он мог бы переходить из текущего состояния в другое состояние без каких-либо входных данных, то есть без ничего, даже {} или фи. И как определение, мы знаем, что ввод должен быть из набора ввода. Надеюсь, это рассеяло ваши сомнения...

person Bhushan Firake    schedule 09.12.2012
comment
Что, если этот переход был в конечное состояние? Как на рисунке 3.51 на странице 225 этого документа univasf.edu.br/~marcus.ramos/lfa-2008-1/Secao%2003-06.pdf . - person liwing; 10.12.2012
comment
Вау... изображение теперь говорит само за себя... как вы видите, q0 переходит в q3 без каких-либо входных данных, и, следовательно, это NFA, и у него есть эпсилон-движения, поэтому это эпсилон-NFA, а не DFA.. - person Bhushan Firake; 10.12.2012
comment
благодарю за разъяснение - person liwing; 10.12.2012

arrow_upward
5
arrow_downward

Из определения DFA: «Детерминированные конечные автоматы — это машина, которая не может перейти в другое состояние, не получая никаких входных данных». И поскольку эпсилон ничего не значит. Следовательно, DFA не может двигаться по эпсилон-движениям.

Принимая во внимание, что из определения NFA «Недетерминированные конечные автоматы - это машина, которая может переходить в другое состояние без получения каких-либо входных данных». Таким образом, NFA может двигаться по эпсилон-ходам.

person SARIKA KESHRI    schedule 17.09.2014

arrow_upward
3
arrow_downward

DFA должен иметь определенный входной символ для перехода из одного состояния в другое. Перемещение эпсилон не разрешено в DFA, так как оно изменит DFA на NFA. Например, предположим, что вы находитесь в состоянии Q1, и у вас есть переход (Q1, e) = Q2, в этом случае вы можете напрямую перейти в Q2 без каких-либо входных данных или вы можете остаться в состоянии Q1, поэтому у вас есть две возможности выбора. в состоянии Q1. В случае DFA у вас не должно быть никаких критериев выбора. Вот почему в DFA нет эпсилон-движений.

person Dibyendu    schedule 09.04.2013