Формальные языки, грамматики и основы построения трансляторов. Кревский И.Г - 35 стр.

UptoLike

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
     управление последовательно передается в следующем порядке через
состояния:
     А, А, В, В, В, А, А, В, А.