2015-04-01
769
В дальнейшем будем рассматривать детерминированный автомат Робина-Скотта (ДРС). Конечным автоматом (ДРС - автоматом) будем называть пятерку A= (X, Z, t, z0, F), где
X – конечное непустое множество входных символов;
Z – конечное непустое множество внутренних состояний;
t – функция переходов: t: Z´X®Z;
z0 – начальное состояние: z0ÎZ;
F - множество конечных состояний: FÌZ.
Пример: A= ({e, a, b}, {z0, z1, z2, z3}, t, z0, {z3}).
t:
входы
| a | b | e | |
| z0 | z0 | z1 | – |
| z1 | z2 | – | z3 |
| z2 | z3 | z1 | – |
| z3 | – | – | – |
По таблице можно построить граф перехода. Вершины графа – состояния А. Дуги помечаются соответствующим элементом множества входов.
 |
Конечный автомат допускает входную цепочку, если эта цепочка переводит его из начального состояния в одно из конечных состояний. Посмотрим, допускает ли автомат цепочку abb?
(z0)®a(z0) ®aa(z0) ®aab(z1) ® aabe(z3)
Определение. Языком, допускаемым автоматом, называется множество допускаемых автоматом цепочек.
Теорема. Для любой автоматной грамматики, порождающей язык, существует автомат, допускающий этот язык.
|
|
|
Обратно: Конечный автомат, является распознающей грамматикой, (т.е. грамматикой, распознающей, является ли данная цепочка цепочкой языка).
Замечание: Множество языков, распознаваемых конечными автоматами, совпадает с множеством автоматных языков.
Вопросы и упражнения
1. Дайте определение языка, допускаемого автоматом.
2. Проверьте, допускает ли автомат А из примера п.п. 5.5 цепочку
ababaa.
