Завтра моя презентация, и я хочу прояснить свои концепции ...
Я прочитал это в DFA: «Для каждого состояния должен быть определен переход на все возможные символы (алфавит)».
Является ли для каждого состояния определение перехода по всем возможным символам обязательным в DFA? Если нет, то приведите, пожалуйста, какие-нибудь примеры?
Ответы:
DFA определяется следующими данными:
Как видно из сигнатуры , он определяет переход в каждом состоянии для каждого символа.δ
источник
Предположим, что DFA было разрешено иметь пропущенные переходы. Что произойдет, если вы встретите символ, для которого не определен переход? Результат не определен. Казалось бы, это нарушает «детерминистическую» характеристику DFA.
Тем не менее, легко превратить такой неполный DFA в полный DFA. Просто добавьте новое состояние
illegal
и отобразите любые неопределенные переходы в этоillegal
состояние. Наконец, добавьте переходы для каждого символа изillegal
состояния обратно в себя. Этоillegal
состояние часто называют состоянием приемника , потому что как только данные попадают в приемник, выходить из него невозможно.Таким образом, с практической точки зрения это спорный вопрос, если у вас есть четко определенный способ обработки пропущенных переходов.
источник
DFA часто определяется как ограниченный тип NFA. ЕслиΣ это входной алфавит и Q является набором состояний, структура перехода NFA указывается как отношение ρ ⊆ Q × Σ × Q или как функция δ: ( Q × Σ ) → 2Q , Если мы примем последнее определение, то мы можем сказать, что NFA является детерминированным, если| δ( д, σ) | ≤ 1 для всех Q∈ Q и σ∈ Σ и завершить, еслиδ( д, σ) ≠ ∅ опять же для всех Q∈ Q и σ∈ Σ ,
Слово принимается NFA, если оно имеет прогон принятия. Детерминированный автомат имеет не более одного запуска. У полного автомата есть хотя бы один прогон.
Некоторые авторы определяют автоматы обрезки как автоматы, в которых каждое состояние находится на некотором пути от начального состояния до конечного состояния. Для некоторых языков у вас не может быть автоматов, которые были бы аккуратными и полными. В этих случаях удобно исключать требование полноты из определения детерминированного автомата.
источник