Презентация на тему Конечные автоматы

Z0, F),
где
Q – конечное множество состояний;
Σ – конечный входной алфавит;
Γ – конечный алфавит магазинных символов;
δ – функция,

переходов, отображение множества Q×(Σ∪{e}∪{⊥})×Γ во множество Q×Γ*;
q0∈Q – начальное состояние;
Z0∈Γ – начальный символ;
F⊆Q – множество заключительных состояний.

часть входной цепочки;
α – содержимое магазина;
«⊥» – маркер конца входной цепочки.

Начальная конфигурация – (q0, w, Z0), где w∈Σ*, заключительная конфигурация – (q, ⊥, α), где q∈F и α∈Γ*.

Z) = (q', γ), где q, q'∈Q, a∈Σ∪{e}∪{⊥}, w∈Σ*,

Z∈Γ, α, γ∈Γ*:
(q, aw, Zα)  (q', w, γα),
Если δ(q, a, Z) = (q', γ), то ДМПА P может:
перейти в состояние q';
сдвинуть головку на одну ячейку вправо;
заменить верхний символ магазина цепочкой γ магазинных символов.
Частные случаи: Z = e, γ = e, a = e, a = ⊥.

множество состояний;
Σ – конечное множество входных символов;
δ – функция переходов, отображение множества Q×(Σ∪{⊥})

во множество Q;
q0∈Q – начальное состояние;
F⊆Q – множество заключительных состояний.

w), где w∈Σ*, заключительная конфигурация – (q, ⊥), где

q∈F.
Такт работы ДКА M при δ(q, a) = q', где q, q'∈Q, a∈Σ∪{⊥}:
(q, aw)  (q', w)

Z) = (q', γ):





Переход ДКА δ(q, a) = q':

δ(q, a) = q', где q'∈F:



Переход ДМПА δ(q, a,

Z) = (q', γ), где q'∈F:

Z) :
(q', γ);
HALT (a = ⊥, q∈F);
ERROR.

:
q';
HALT (a = ⊥, q∈F);
ERROR.

преобразовать его в таблицу переходов.
2. Построение графа начинается с

начального состояния q0. Если начальное состояние может являться также и конечным, помечаем это двойной границей окружности.
3. Для каждого состояния графа qi определяем, есть ли из данного состояния такие переходы (a, Z, γ), которые соответствуют допустимому символу a из входной цепочки и допустимому символу Z на вершине стека (если автомат с магазинной памятью), которые пока еще отсутствуют в графе. Если есть, то проверяем, ведет ли данный переход в уже имеющееся состояние. Если да, то добавляем в граф только новый переход (a, Z, γ). Если нет, то добавляем в граф новое состояние и переход (a, Z, γ) в него. Если новое состояние может являться конечным, помечаем это двойной границей окружности.
4. Если в процессе выполнения шага 3 в графе появились новые состояния или переходы, возвращаемся на шаг 3, иначе граф переходов построен.

a, Z) = (q', γ, 〈A〉).
Функция переходов ДКА:
δ(q, a)

= (q', 〈A〉).
Отсутствие действия:
〈A〉 = e или 〈A〉 = ∅.

– входная цепочка. Тогда:
1. q := q0, M :=

Z0, k := 1.
2. Ищем δ(q, a, Z), где: a = ak, M = Zβ или a = ak, Z = e или a = e, M = Zβ.
3. Если δ(q, a, Z) не определена, то ошибка в позиции k. Если значений δ(q, a, Z) несколько – таблица переходов построена неверно. Если δ(q, a, Z) = (q', γ, 〈A〉), то:
3.1. Если 〈A〉 ≠ e и 〈A〉 ≠ ∅, то выполнить действие 〈A〉.
3.2. q := q'.
3.3. M := γβ.
3.4. Если a ≠ e, то k := k + 1.
4. Если δ(q, a, Z) = HALT, то разбор успешно завершен.
5. Если δ(q, a, Z) = ERROR, то имеем во входной цепочке синтаксическую ошибку в позиции k.

q := q0, k := 1.
2. Ищем δ(q, a),

где a = ak.
3. Если δ(q, a) не определена, то ошибка в позиции k. Если значений δ(q, a) несколько – таблица переходов построена неверно. Если δ(q, a) = (q', 〈A〉), то:
3.1. Если 〈A〉 ≠ e и 〈A〉 ≠ ∅, то выполнить действие 〈A〉.
3.2. q := q'.
3.3. k := k + 1.
4. Если δ(q, a) = HALT, то разбор успешно завершен.
5. Если δ(q, a) = ERROR, то имеем во входной цепочке синтаксическую ошибку в позиции k.

N – целая, а M – дробная часть числа.

символов алфавита.

(Q, Σ, δ, q0, F), где:
Q = {q0, q1,

q2, q3, q4};
Σ = {+, –, ., 0-9};
δ(Q×Σ) = {{q1, q2, q3, ERROR}, {ERROR, q2, q3, ERROR}, {ERROR, ERROR, q5, ERROR}, {ERROR, q4, q3, HALT}, {ERROR, ERROR, q4, HALT}};
F = {q3, q4}.

«–15.2⊥») 1 (q1, «15.2⊥»)
2 (q3, «5.2⊥»)

3 (q3, «.2⊥»)
4 (q4, «2⊥»)
5 (q4, «⊥»)
6 HALT
Разбор завершен успешно. Другой пример:
(q0, «.2.⊥») 1 (q2, «2.⊥»)
2 (q4, «.⊥»)
3 ERROR
Имеем синтаксическую ошибку в позиции 3.

– count := 1;
〈A2〉 – count := count +

1; если count > N, δ(q, a) = ERROR.

Σ, Γ, δ, q0, Z0, F), где:
Q = {q0,

q1, q2};
Σ = {(, ), _, a-z, A-Z, 0-9};
Γ = {(} ;
δ(Q×(Σ∪{e}∪{⊥})×Γ) = {{(q0, «(»), (q1, e), ERROR, ERROR, ERROR}, {ERROR, (q1, e), (q1, e), (q2, e), HALT}, {ERROR, ERROR, ERROR, (q2, e), HALT}};
Z0 = e;
F = {q1, q2}.

e) 1 (q0, «(a123))⊥», «(»)

2 (q0, «a123))⊥», «((»)
3 (q1, «123))⊥», «((»)
4 (q1, «23))⊥», «((»)
5 (q1, «3))⊥», «((»)
6 (q1, «))⊥», «((»)
7 (q2, «)⊥», «(»)
8 (q2, «⊥», e)
9 HALT
Разбор завершен успешно.

e) 1 (q0, «x))⊥»,

«(»)
2 (q1, «))⊥», «(»)
3 (q1, «)⊥», e)
4 ERROR
Имеем ошибку в позиции 4. Пример разбора цепочки «()»:
(q0, «()⊥», e) 1 (q0, «)⊥», «(»)
2 ERROR
Ошибка в позиции 2.

языка Pascal «begin end;». Таблица переходов ДМПА при посимвольном

разборе:

по лексемам:



Σ = {b, e, g, i, n, d,

«;», _} → Σ' = {begin, end, «;»}

три подмножества:
1. Подмножество символов-разделителей ΣS⊂Σ;
2. Подмножество символов пунктуации ΣP⊂Σ;
3.

Подмножество лексемных символов ΣL⊂Σ:
ΣL = Σ – (ΣS∪ΣP).
Алфавит Σ':
Σ'⊆ΣP∪ΣL+.
Лексема x – либо x∈ΣP, либо x∈ΣL+, отделенная от других лексем символами алфавитов ΣS и ΣP.

(1:1);
2. begin (2:3);
3. end (2:9);
4. ; (2:13);
5. end (3:1);
6.

; (3:4);
7. begin (4:1);
8. end (5:1);
9. ; (5:4).

e) 1 (q0, «be;e;be;⊥», b)

2 (q0, «e;e;be;⊥», bb)
 3 (q1, «;e;be;⊥», b)
4 (q0, «e;be;⊥», b)
5 (q1, «;be;⊥», e)
6 (q0, «be;⊥», e)
7 (q0, «e;⊥», b)
8 (q1, «;⊥», e)
9 (q0, «⊥», e)
10 HALT

(1:7);
3. ; (1:10);
4. end (2:1);
5. ; (2:4);
(q0,

«be;e;⊥», e) 1 (q0, «e;e;⊥», b)
2 (q1, «;e;⊥», e)
 3 (q0, «e;⊥», e)
4 ERROR