Введение в теорию формальных языков и грамматик. Лекция 2

1.

Лекция 2
1
Введение в теорию
формальных языков и
грамматик
Разработал: к.п.н., доцент
Наточая Е. Н.

2.

План лекции
2
1 Основные понятия теории формальных
языков
2 Операции над цепочками символов
3 Формальные грамматики
4 Формы Бэкуса - Наура
5 Диаграммы Вирта

1 Основные понятия теории формальных языков
3
Алфавит V
Цепочка в алфавите V
Пустая цепочка
Цепочка в алфавите V формально
1) - цепочка в V;
2) если - цепочка в V ; а V,
то а – цепочка в V;
3) - цепочка в V 1) и 2).

4.

2 Операции над цепочками символов
4
Длина цепочки - | |.
Конкатенация и - =
: = =
Степень n цепочки - n
: 0= и n= n-1 = n-1 для n 1
Реверс - R
Пример 1
V={a, b, c, d}; цепочки в V: =ab и =bcd;
| |=2, | |=3; = abbcd; 2=abab; R=dcb.

5.

Основные понятия
теории формальных языков
5
Обозначения: V*; V+
Формальный язык L V*
Пример 2
V={0, 1}; V*={ , 0, 1, 00, 01, 10, 11, 000, …};
V+={0, 1, 00, 01, 10, 11, 000, …}.

6.

Способы задания формальных языков:
6
язык множеств;
генерация строк (грамматики,
формы Бэкуса-Наура и диаграммы Вирта);
распознаватели.
Пример 2
L={0n1n | n 0}

7.

3 Формальные грамматики
7
Грамматика G (VT , VN , P, S ),
где 1) VT V;
2) VN V, VT VN = ;
3) Р (VT VN)+ (VT VN)*;( , ): ;
4) S VN.
Сокращения: 1, 2 , , n
1 | 2 | | n
Пример 3
G1=({0, 1}, {A, S}, P1, S), где
Р1: 1) S 0A1; 2) 0A 00A1; 3) A .

8.

Выводимость цепочек
8
(VT VN)* непосредственно выводима из
(VT VN)+ в G(VT, VN, P, S)
=ξ1γξ2, β= ξ1δξ2; ξ1, ξ2, δ (VT VN)*,
γ (VT VN)+ и γ δ P.
Обозначается:
(VT VN)* выводима из (VT VN)+ в
G(VT, VN, P, S) γ0, γ1, …, γn (n 0):
= γ0 γ1 … γn = .
Обозначается *

9.

Пример 4
9
G1=({0, 1}, {A, S}, P1, S), где
Р1: 1) S 0A1; 2) 0A 00A1; 3) A .
S *000111, т.к. S 0А1 00А11 000А111
000111
Язык грамматики L(G)={ VT* | S * }
Пример 5
L(G1)={0n1n | n>0}
Сентенция G V *: S *

10.

4 Формы Бэкуса - Наура
10
Метаязык БНФ:
::= ; < > ; | ; [ ] ; { } ; {/ / } ; ( ) ; “ “.
Пример 6
Правила, определяющие понятие
«идентификатор»:
<идентификатор> ::= <буква> { (<буква> | <цифра>) }
<буква> ::= a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p |
q|r|s|t|u|v|w|x|y|z
<цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Введение в теорию формальных языков и грамматик. Лекция 2

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.