Языки и трансляции. Мартыненко Б.К. - 30 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

29
Запись δ(
q, a)=p, где q,p ∈Q и a∈Σ, означает, что конечный автомат M в
состоянии
q, сканируя входной символ a, продвигает свою входную головку на
одну ячейку вправо и переходит в состояние
p.
Область определения отображения δ можно расширить до
Q × Σ
*
следу-
ющим образом: δ
’
(q, ε) = q, δ
’
(q, xa) = δ(δ
’
(q, x), a) для любого x ∈ Σ
*
и a ∈ Σ.
Таким образом, запись δ
’
(q, x) = p означает, что fa M, начиная в состоянии q∈Q
чтение цепочки
x∈Σ
*
, записанной на входной ленте, оказывается в состоянии
p∈Q, когда его входная головка продвинется правее цепочки x.
Далее мы будем использовать одно и то же обозначение δ для обоих
отображений, так как это не приведёт к путанице.
Определённая таким образом модель конечного автомата называется
детерминированной. Для обозначения детерминированного автомата часто
используют аббревиатуру dfa (
deterministic finite automaton).
Определение 3.2. Цепочка x ∈Σ
*
принимается конечным автоматом M,
если δ(
q
0
, x)=p для некоторого p∈F.
Множество всех цепочек x∈ Σ
*
, принимаемых конечным автоматом M,
называется языком, распознаваемым конечным автоматом M, и обозначается
как
T(M), т. е.
T(M) = {x∈Σ
*
| δ(q
0
, x) = p при некотором p∈F}.
Любое
множество цепочек, принимаемых конечным автоматом, называется
регулярным.
Пример 3.1. Рассмотрим диаграмму состояний конечного автомата. Пусть
задан
конечный автомат M = (Q, Σ, δ, q
0
, F), где Q = {q
0
, q
1
, q
2
, q
3
}, Σ = {0, 1},
F = {q
0
}, δ(q
0
, 0) = q
2
, δ(q
0
, 1) = q
1
, δ(q
1
, 0) = q
3
, δ(q
1
, 1) = q
0
,
δ(
q
2
, 0) = q
0
, δ(q
2
, 1) = q
3
, δ(q
3
, 0) = q
1
, δ(q
3
, 1) = q
2.
Диаграмма состояний конечного автомата состоит из узлов, пред-
ставляющих состояния, и из ориентированных дуг, определяющих возможные
переходы, которые зависят от входных символов. Так, если δ(
q, a) = p, то из
узла, представляющего
состояние q, в узел, представляющий состояние p,
проводится дуга, помеченная входным символом a. На рис.3.2 дана диаграмма
состояний конечного автомата
M. Двойным кружком выделено единственное в
данном примере конечное состояние, которое является одновременно и
начальным.
Рис. 3.2.

Страницы