ВУЗ:
Составители:
35
6. КОНЕЧНЫЕ АВТОМАТЫ
Существует полное соответствие между регулярными выражениями (а
поэтому и грамматиками типа 3) и конечными автоматами, которые
определяются следующим образом:
Конечный автомат
– это устройство для распознавания строк какого-
либо языка. У него есть конечное множество состояний, отдельные из
которых называются последними. По мере считывания каждой литеры
строки контроль передается от состояния к состоянию в соответствии с
заданным множеством переходов. Если после считывания последней литеры
строки автомат будет находиться в одном из последних
состояний, о строке
говорят, что она принадлежит языку, принимаемому автоматом. В ином
случае строка не принадлежит языку, принимаемому автоматом.
Конечный автомат формально определяется пятью характеристиками:
-конечным множеством состояний ( K )
-конечным входным алфавитом (
Σ
)
-множеством переходов (
δ
)
-начальным состоянием ( S
0
∈ K )
-множеством последних состояний ( f ∈ K )
M = ( K ,
Σ
,
δ
, S
0
, f ).
Пример:
Состояниями автомата являются А и В, входным алфавитом –
{0,1}, начальным состоянием – А, множеством последних состояний – {A}, а
переходами
δ
(А, 0) = А,
δ
(А, 1) = В,
δ
(В, 0) = В,
δ
(В, 1) = А.
Эти переходы означают , что при чтении 0 в состоянии А управление
передается в состояние А и т.д. При чтении строки
0 1 0 0 1 0 1 1
управление последовательно передается в следующем порядке через
состояния:
А, А, В, В, В, А, А, В, А.
35 6. КОНЕЧНЫЕ АВТОМАТЫ Существует полное соответствие между регулярными выражениями (а поэтому и грамматиками типа 3) и конечными автоматами, которые определяются следующим образом: Конечный автомат – это устройство для распознавания строк какого- либо языка. У него есть конечное множество состояний, отдельные из которых называются последними. По мере считывания каждой литеры строки контроль передается от состояния к состоянию в соответствии с заданным множеством переходов. Если после считывания последней литеры строки автомат будет находиться в одном из последних состояний, о строке говорят, что она принадлежит языку, принимаемому автоматом. В ином случае строка не принадлежит языку, принимаемому автоматом. Конечный автомат формально определяется пятью характеристиками: -конечным множеством состояний ( K ) -конечным входным алфавитом ( Σ ) -множеством переходов ( δ ) -начальным состоянием ( S0 ∈ K ) -множеством последних состояний ( f ∈ K ) M = ( K , Σ , δ , S0 , f ). Пример: Состояниями автомата являются А и В, входным алфавитом – {0,1}, начальным состоянием – А, множеством последних состояний – {A}, а переходами δ (А, 0) = А, δ (В, 0) = В, δ (А, 1) = В, δ (В, 1) = А. Эти переходы означают , что при чтении 0 в состоянии А управление передается в состояние А и т.д. При чтении строки 01001011 управление последовательно передается в следующем порядке через состояния: А, А, В, В, В, А, А, В, А.
Страницы
- « первая
- ‹ предыдущая
- …
- 33
- 34
- 35
- 36
- 37
- …
- следующая ›
- последняя »