Стр. 76 - Информационные структуры и их преобразование

74 Содержание
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
000111 bbbbaaa
S=> 0AS, SAa =>00SAS, SASaa =>000ASAS, SASAaaa => 0001111,
bbbbaaa.
Необходима индексация.
Простые СУ – переводы образуют важный класс трансляторов, так как
легко реализуются преобразованиями с магазинной памятью.
5.3. Конечные преобразователи. (Простейший транслятор)
В его основе лежит конечный автомат.
Конечный преобразователь:
M= {Q, Σ, ∆, δ0, q0 , F},
где Q – множество состояний;
Σ - входной алфавит;
∆ - выходной алфавит;
δ0 – функция отображения;
q 0 – начальное состояние;
F – множество заключительных состояний.
Q * Σие -> Q*∆*.
Конфигурация определяется: (q, x, y).
Если δ(q0, a)= δ(q1 , b), то (q0, ax, y)|- (q 1, x, yb).
Цепочка y называется выходом цепочки x, если имеет место
следующее:
(q0, x, y)|--- (q 1, x, y), где x ∈ Σ*, y ∈ A* , q1 ∈ F
|--- вывод за какое-то количество шагов.
Перевод, определяемый конечными преобразованиями, называется
регулярным («правильным»): S:= a + S |a-S| -a | +a | a.
СУ
Только
Только
+
+