Математическая логика и теория алгоритмов. Стенюшкина В.А. - 101 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

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

Рубрика: 

Таблица служебных слов Таблица разделителей
N Служебное
слово
N Значение конста-
нты
1 Program 1 ;
2 Begin 2 ,
3 End 3 +
4 For 4 -
5 Integer … ……………………
6 Var 9 .
… … ……………………
В качестве кодов типов лексем используются числа: 10(служебное сло-
во), 20(разделитель), 30(идентификатор), 40(константа).
6.6 Регулярные языки. Конечные автоматы
Порождающая грамматика G=<N, T, P, S> называется регулярной, если
её правила имеют вид: A
→aB или C→b, где A, B, C∈N, ab∈T. Язык L(G), по-
рождаемый регулярной грамматикой, называется регулярным языком.
Пример – G=<N, T, P, S>: N={I, K}, T={
δ, u}, S={I}, P={I δ,
I
δK, K δK, K uK, K v, K u}, где δ, u – терминальные
символы для обозначения букв и цифр соответственно, является регулярной
грамматикой, порождающей идентификаторы. Идентификатором называется
последовательность букв и цифр, начинающихся с буквы. В частности, иденти-
фикатор <
δδuδu > порождается цепочкой: I b K δ δ K δ δ u K δ δ
u b K
δ δ u δ u .
Поскольку основной задачей ЛА является распознавание лексических
единиц, рассмотрим одну из математических моделей распознавателя регуляр-
ного языка – конечный автомат (КА).
Конечным автоматом называется пятёрка A=< V, Q,
δ, q
0
F >, где V={a
1
,
… ,a
m
} – входной алфавит, Q={q
0
, q
1
, … , q
n-1
} – алфавит состояний, δ: Q×V→Q
– функция переходов, q
0
– начальное состояние КА, F⊂Q – множество конеч-
ных состояний.
Графическое представление отображения
δ называется диаграммой сос-
тояний конечного автомата а. Это – ориентированный граф, вершины которого
поставлены в соответствие символы алфавита состояний, а другим символы
входного алфавита.
Пример – Конечный автомат для грамматики предыдущего примера
имеет вид: A=< V, Q,
δ, q
0
F >, гдеV=T={δ, u}, Q=N∪{Z}={I, K, Z}, q
0
={S}={I},
f={Z}. Его можно представить диаграммой состояний (рисунок 6.1). 
      Таблица служебных слов                   Таблица разделителей

         N           Служебное                   N          Значение конста-
             слово                                   нты
         1           Program                     1          ;
         2           Begin                       2          ,
         3           End                         3          +
         4           For                         4          -
         5           Integer                     …          ……………………
         6           Var                         9          .
         …                                       …          ……………………

        В качестве кодов типов лексем используются числа: 10(служебное сло-
во), 20(разделитель), 30(идентификатор), 40(константа).

      6.6 Регулярные языки. Конечные автоматы

       Порождающая грамматика G= называется регулярной, если
её правила имеют вид: A→aB или C→b, где A, B, C∈N, ab∈T. Язык L(G), по-
рождаемый регулярной грамматикой, называется регулярным языком.
       Пример – G=: N={I, K}, T={δ, u}, S={I}, P={I              δ,
I     δK, K      δK, K       uK, K     v, K        u}, где δ, u – терминальные
символы для обозначения букв и цифр соответственно, является регулярной
грамматикой, порождающей идентификаторы. Идентификатором называется
последовательность букв и цифр, начинающихся с буквы. В частности, иденти-
фикатор < δδuδu > порождается цепочкой: I       bK      δδK       δδuK      δδ
ubK      δδuδu.
       Поскольку основной задачей ЛА является распознавание лексических
единиц, рассмотрим одну из математических моделей распознавателя регуляр-
ного языка – конечный автомат (КА).
       Конечным автоматом называется пятёрка A=< V, Q, δ, q0F >, где V={a1,
… ,am} – входной алфавит, Q={q0, q1, … , qn-1} – алфавит состояний, δ: Q×V→Q
– функция переходов, q0 – начальное состояние КА, F⊂Q – множество конеч-
ных состояний.
       Графическое представление отображения δ называется диаграммой сос-
тояний конечного автомата а. Это – ориентированный граф, вершины которого
поставлены в соответствие символы алфавита состояний, а другим символы
входного алфавита.
       Пример – Конечный автомат для грамматики предыдущего примера
имеет вид: A=< V, Q, δ, q0F >, гдеV=T={δ, u}, Q=N∪{Z}={I, K, Z}, q0={S}={I},
f={Z}. Его можно представить диаграммой состояний (рисунок 6.1).

Страницы