Составители:
28
Глава 3
КОНЕЧНЫЕ АВТОМАТЫ
И РЕГУЛЯРНЫЕ ГРАММАТИКИ
§ 3.1. Конечный автомат
В гл. 2 мы познакомились со схемой порождения — грамматиками.
Грамматики являются конечными описаниями языков. В этой главе мы
рассмотрим другой метод конечного описания бесконечных языков — с
помощью
распознавателей, наипростейшим примером которых являются
конечные автоматы.
Конечный автомат (рис.3.1) состоит из конечного управления и входной
ленты, разбитой на ячейки. В каждой ячейке записан один символ из входного
алфавита Σ, и все они образуют конечную входную цепочку. Конечное
управление первоначально находится в состоянии
q
0
и сканирует крайнюю
левую ячейку ленты. По мере чтения входной цепочки слева направо автомат
переходит в другие состояния из множества
Q. Если, прочитав входную
цепочку, автомат оказывается в некотором конечном состоянии из множества
F, то говорят, что он принял её. Множество цепочек, принимаемых конечным
автоматом, называется языком, распознаваемым данным конечным
автоматом
.
Конечные автоматы не могут распознавать все языки, порождаемые
грамматиками,
но языки, распознаваемые ими, являются в точности языками,
порождаемыми грамматиками типа 3. В последующих главах мы познакомимся
с распознавателями для языков типа 0, 1 и 2. В дальнейшем вместо термина
“конечный автомат” будем использовать аббревиатуру fa —
finite automaton.
Здесь мы определим конечный автомат как формальную систему и выяс-
ним его возможности как распознающего устройства.
Определение 3.1. Конечным автоматом называется формальная система
M = (Q, Σ, δ, q
0
, F), где Q — конечное непустое множество состояний, Σ —
конечный
входной алфавит, δ — отображение типа Q × Σ → Q, q
0
∈Q —
начальное состояние, F ⊆ Q — множество конечных состояний.
a
2
…
a
i
…
a
n
Вхо
д
ная лента: a
i
∈
Конечное
управление
Q × Σ → Q
a
1
Рис. 3.1.
q
i
∈Q
q
0
∈
Q
q
n
∈
F
Страницы
- « первая
- ‹ предыдущая
- …
- 27
- 28
- 29
- 30
- 31
- …
- следующая ›
- последняя »
