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

UptoLike

ВУЗ: 

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

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

Рубрика: 

11
ТИП 2:
Грамматика G = (VT, VN, P, S) называется контекстно-свободной (КС), если
каждое правило из Р имеет вид: A → β, где A ∈ VN, β ∈ (VT ∪ VN)
+
.
Грамматика G = (VT, VN, P, S) называется укорачивающей контекстно-
свободной (УКС), если каждое правило из Р имеет вид: A → β, где A ∈ VN,
β ∈ (VT ∪ VN)
*
.
Грамматику типа 2 можно определить как контекстно-свободную либо
как укорачивающую контекстно-свободную. Возможность выбора обусловлена
тем, что для каждой УКС-грамматики существует почти эквивалентная
КС-грамматика.
ТИП 3:
Грамматика G = (VT, VN, P, S) называется праволинейной, если каждое правило
из Р имеет вид: A → tB либо A → t, где A ∈ VN, B ∈ VN, t ∈ VT.
Грамматика G = (VT, VN, P, S) называется леволинейной, если каждое правило
из Р имеет вид: A → Bt либо A → t, где A ∈ VN, B ∈ VN, t ∈ VT.
Грамматику типа 3 (регулярную, Р-грамматику) можно определить как
праволинейную либо как леволинейную. Выбор определения не влияет на мно-
жество языков, порождаемых грамматиками этого класса, поскольку доказано,
что множество языков, порождаемых праволинейными грамматиками, совпада-
ет с множеством языков, порождаемых леволинейными грамматиками.
Соотношения между типами грамматик:
(1) любая регулярная грамматика является КС-грамматикой;
(2) любая регулярная грамматика является УКС-грамматикой;
(3) любая КС-грамматика является КЗ-грамматикой;
(4) любая КС-грамматика является неукорачивающей грамматикой;
(5) любая КЗ-грамматика является грамматикой типа 0;
(6) любая неукорачивающая грамматика является грамматикой типа 0.
Замечание: УКС-грамматика, содержащая правила вида A → λ, не являет-
ся КЗ-грамматикой и не является неукорачивающей грамматикой.
Язык L(G) является языком типа k, если его можно описать грамматикой
типа k. Если язык задан грамматикой типа k, то это не значит, что не существу-
ет грамматики типа k’ (k’>k), описывающей тот же язык. Поэтому, когда гово-
рят о языке типа k, обычно имеют в виду максимально возможный номер k.
Соотношения между типами языков:
(1) каждый регулярный язык является КС-языком, но существуют
КС-языки, которые не являются регулярными (например, L = {a
n
b
n
| n>0}).
(2) каждый КС-язык является КЗ-языком, но существуют КЗ-языки, кото-
рые не являются КС-языками (например, L = {a
n
b
n
c
n
| n>0}).
(3) каждый КЗ-язык является языком типа 0.
Замечание: УКС-язык, содержащий пустую цепочку, не является КЗ-языком.

Страницы