Теория формальных языков, грамматик и автоматов. Ишакова Е.Н. - 4 стр.

UptoLike

ВУЗ: 

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

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

Рубрика: 

4
1 Лабораторная работа № 1. Распознавание типов формаль-
ных языков и грамматик
Цель: - закрепить понятия «алфавит», «цепочка», «формальная грамма-
тика» и «формальный язык», «выводимость цепочек», «эквивалентная грамма-
тика»;
- сформировать умения и навыки распознавания типов формаль-
ных языков и грамматик по классификации Хомского, построения эквивалент-
ных грамматик.
Основы теории
Определение 1.1. Алфавитом V называется конечное множество симво-
лов.
Определение 1.2. Цепочкой
α
в алфавите V называется любая конечная
последовательность символов этого алфавита.
Определение 1.3. Цепочка, которая не содержит ни одного символа, назы-
вается пустой цепочкой и обозначается
ε
.
Определение 1.4. Формальное определение цепочки символов в алфавите
V:
1)
ε
- цепочка в алфавите V;
2) если
α
- цепочка в алфавите V и а – символ этого алфавита, то
α
а – це-
почка в алфавите V;
3)
β
- цепочка в алфавите V тогда и только тогда, когда она является та-
ковой в силу утверждений 1) и 2).
Определение 1.5. Длиной цепочки
α
называется число составляющих ее
символов (обозначается |
α
|).
Обозначим через V
*
множество, содержащее все цепочки в алфавите V,
включая пустую цепочку
ε
, а через V
+
- множество, содержащее все цепочки в
алфавите V, исключая пустую цепочку
ε
.
Пример 1.1. Пусть
}0,1{=
V
, тогда },000,11,10,01,00,1,0,{
*
K
ε
=V , а
},000,11,10,01,00,1,0{ K=
+
V .
Определение 1.6. Формальной грамматикой называется четверка вида:
),,,( SPVVG
N
T
= , (1.1)
где V
N
- конечное множество нетерминальных символов грамматики
(обычно прописные латинские буквы);
V
T
- множество терминальных символов грамматики (обычно строч-
ные латинские буквы, цифры, и т.п.), V
T
∩V
N
=
∅
;
Р – множество правил вывода грамматики, являющееся конечным
подмножеством множества (V
T
∪ V
N
)
+
× (V
T
∪ V
N
)
*
; элемент
(
α
,
β
) множества Р называется правилом вывода и записывает-
    1 Лабораторная работа № 1. Распознавание типов формаль-
ных языков и грамматик

     Цель: - закрепить понятия «алфавит», «цепочка», «формальная грамма-
тика» и «формальный язык», «выводимость цепочек», «эквивалентная грамма-
тика»;
            - сформировать умения и навыки распознавания типов формаль-
ных языков и грамматик по классификации Хомского, построения эквивалент-
ных грамматик.
                                        Основы теории
       Определение 1.1. Алфавитом V называется конечное множество симво-
лов.
     Определение 1.2. Цепочкой α в алфавите V называется любая конечная
последовательность символов этого алфавита.
 Определение 1.3. Цепочка, которая не содержит ни одного символа, назы-
                 вается пустой цепочкой и обозначается ε.
     Определение 1.4. Формальное определение цепочки символов в алфавите
V:
     1) ε - цепочка в алфавите V;
     2) если α - цепочка в алфавите V и а – символ этого алфавита, то αа – це-
почка в алфавите V;
     3) β - цепочка в алфавите V тогда и только тогда, когда она является та-
ковой в силу утверждений 1) и 2).
     Определение 1.5. Длиной цепочки α называется число составляющих ее
символов (обозначается | α |).
     Обозначим через V* множество, содержащее все цепочки в алфавите V,
включая пустую цепочку ε, а через V+ - множество, содержащее все цепочки в
алфавите V, исключая пустую цепочку ε.
       Пример 1.1. Пусть V = {1, 0} , тогда V * = {ε , 0, 1, 00, 01, 10, 11, 000, K} , а
V + = {0, 1, 00, 01, 10, 11, 000, K} .
      Определение 1.6. Формальной грамматикой называется четверка вида:

             G = (VT , V N , P, S ) ,                                             (1.1)

       где VN - конечное множество нетерминальных символов грамматики
                (обычно прописные латинские буквы);
           VT - множество терминальных символов грамматики (обычно строч-
                ные латинские буквы, цифры, и т.п.), VT ∩VN =∅;
           Р – множество правил вывода грамматики, являющееся конечным
                подмножеством множества (VT ∪ VN)+ × (VT ∪ VN)*; элемент
                (α, β) множества Р называется правилом вывода и записывает-

4

Страницы