У цьому розділі ми обговоримо метод перетворення NFA в його еквівалент DFA. У NFA, коли певний вхід надається поточному стану, машина переходить до кількох станів. Він може мати нуль, один або більше ніж один хід на заданому вхідному символі. З іншого боку, у DFA, коли в поточний стан подається певний вхід, машина переходить лише в один стан. DFA має лише один хід на даному вхідному символі.
Нехай M = (Q, ∑, δ, q0, F) є НФА, який приймає мову L(M). Повинен існувати еквівалентний DFA, позначений M' = (Q', ∑', q0', δ', F'), такий, що L(M) = L(M').
Кроки для перетворення NFA на DFA:
Крок 1: Спочатку Q' = ϕ
крок 2: Додайте q0 NFA до Q'. Потім знайдіть переходи з цього початкового стану.
крок 3: У Q' знайдіть можливий набір станів для кожного вхідного символу. Якщо цього набору станів немає в Q', додайте його до Q'.
ipconfig для ubuntu
крок 4: У DFA кінцевим станом будуть усі стани, які містять F (кінцеві стани NFA)
приклад 1:
Перетворіть заданий NFA на DFA.
рішення: Для наведеної діаграми переходів спочатку побудуємо таблицю переходів.
| Держава | 0 | 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | {q1, q2} | q1 |
| *q2 | q2 | {q1, q2} |
Тепер ми отримаємо δ' перехід для стану q0.
δ'([q0], 0) = [q0] δ'([q0], 1) = [q1]
Перехід δ' для стану q1 отримується як:
створення столів з латексу
δ'([q1], 0) = [q1, q2] (new state generated) δ'([q1], 1) = [q1]
Перехід δ' для стану q2 отримується як:
δ'([q2], 0) = [q2] δ'([q2], 1) = [q1, q2]
Тепер ми отримаємо δ' перехід на [q1, q2].
δ'([q1, q2], 0) = δ(q1, 0) ∪ δ(q2, 0) = {q1, q2} ∪ {q2} = [q1, q2] δ'([q1, q2], 1) = δ(q1, 1) ∪ δ(q2, 1) = {q1} ∪ {q1, q2} = {q1, q2} = [q1, q2] Стан [q1, q2] також є кінцевим станом, оскільки він містить кінцевий стан q2. Таблиця переходів для побудованого DFA буде виглядати так:
| Держава | 0 | 1 |
|---|---|---|
| →[q0] | [q0] | [q1] |
| [q1] | [q1, q2] | [q1] |
| *[q2] | [q2] | [q1, q2] |
| *[q1, q2] | [q1, q2] | [q1, q2] |
Діаграма переходу буде виглядати так:
Стан q2 можна усунути, оскільки q2 є недосяжним станом.
оновлення від join sql
приклад 2:
Перетворіть заданий NFA на DFA.
рішення: Для наведеної діаграми переходів спочатку побудуємо таблицю переходів.
| Держава | 0 | 1 |
|---|---|---|
| →q0 | {q0, q1} | {q1} |
| *q1 | ϕ | {q0, q1} |
Тепер ми отримаємо δ' перехід для стану q0.
δ'([q0], 0) = {q0, q1} = [q0, q1] (new state generated) δ'([q0], 1) = {q1} = [q1] Перехід δ' для стану q1 отримується як:
δ'([q1], 0) = ϕ δ'([q1], 1) = [q0, q1]
Тепер ми отримаємо δ' перехід на [q0, q1].
δ'([q0, q1], 0) = δ(q0, 0) ∪ δ(q1, 0) = {q0, q1} ∪ ϕ = {q0, q1} = [q0, q1] Так само
δ'([q0, q1], 1) = δ(q0, 1) ∪ δ(q1, 1) = {q1} ∪ {q0, q1} = {q0, q1} = [q0, q1] Оскільки в даному NFA q1 є кінцевим станом, тоді в DFA будь-де, де існує q1, цей стан стає кінцевим станом. Отже, у DFA кінцевими станами є [q1] і [q0, q1]. Тому множина кінцевих станів F = {[q1], [q0, q1]}.
b+ дерева
Таблиця переходів для побудованого DFA буде виглядати так:
| Держава | 0 | 1 |
|---|---|---|
| →[q0] | [q0, q1] | [q1] |
| *[q1] | ϕ | [q0, q1] |
| *[q0, q1] | [q0, q1] | [q0, q1] |
Діаграма переходу буде виглядати так:
Навіть ми можемо змінити назву штатів DFA.
Припустимо
A = [q0] B = [q1] C = [q0, q1]
З цими новими назвами DFA матиме такий вигляд:
