Системное программное обеспечение: Основы трансляции. Карпушин А.Н - 4 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

6
1. Основы теории формальных языков
Основные понятия и определения
Алфавит – это некоторое конечное множество символов.
Цепочка символов в алфавите V – любая конечная последовательность
символов этого алфавита. Цепочка, которая не содержит ни одного символа,
называется пустой цепочкой, обозначается символом λ.
Если α и β – цепочки, то цепочка αβ называется конкатенацией (или сцеп-
лением) цепочек α и β. Если α = ab и β = cd, то αβ = abcd. Для любой цепочки α
выполняется: αλ = λα = α.
Обращением (или реверсом) цепочки α называется цепочка, символы кото-
рой записаны в обратном порядке. Обращение цепочки α будем обозначать α
R
.
n-ой степенью цепочки α (обозначается α
n
) называется конкатенация n це-
почек α. α
0
= λ; α
n
= αα
n-1
= α
n-1
α.
Длина цепочки – число составляющих ее символов. Обозначается |α|.
Язык в алфавите V – это подмножество цепочек конечной длины в этом
алфавите.
Обозначим через V
*
множество, содержащее все цепочки в алфавите V,
включая пустую цепочку. Т.е., если V={0,1}, то V
*
= {λ,0,1,00,11,01,10,000,001,
011,…}.
Обозначим через V
+
множество, содержащее все цепочки в алфавите V,
исключая пустую цепочку. Следовательно, V
*
= V
+
∪ {λ}.
Каждый язык в алфа-
вите V является подмножеством множества V
*
.
Существует несколько способов описания языков. Рассмотрим один из
них – использующий порождающие грамматики.
Порождающая грамматика G – это четверка (VT, VN, P, S), где:
VT – алфавит терминальных символов (терминалов),
VN – алфавит нетерминальных символов (нетерминалов), не пересе-
кающийся с VT,
P – конечное подмножество множества (VT ∪ VN)
+
х (VT ∪ VN)
*
;
элемент (α, β) множества P называется правилом вывода и записывается в
виде α → β,
S – начальный символ (цель) грамматики, S ∈ VN.
Для записи правил вывода с одинаковыми левыми частями:
α → β
1,
α → β
2,
..., α → β
n
можно пользоваться сокращенной записью:
α → β
1
| β
2
|...| β
n
.
Каждое β
i
, i= 1, 2, ... ,n , называется альтернативой правила вывода из
цепочки α.
Пример грамматики:
G1 = ({0,1}, {A,S}, P, S),
где P состоит из правил:
S
→
0A1
,
0A
→
00A1
,
A
→
λ
.

Страницы