Языки и трансляции. Мартыненко Б.К. - 20 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

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

Рубрика: 

19
II.
Достаточность (индукция по длине цепочки l ≥ 1). Докажем по индук-
ции для любой цепочки
x∈ {a, b}
+
, такой что |x| = l, и для любого l ≥ 1, что
1) если #
a
x = #
b
x, то существует вывод S
x;
2) если #
a
x = #
b
x + 1, то существует вывод A
x;
3) если #
a
x = #
b
x − 1, то существует вывод B
x.
База (l = 1). Утверждение 1) доказывать нет необходимости, т. к. цепочек
длины 1, удовлетворяющих условию 1) не существует.
Условиям 2) и 3) удовлетворяют цепочки
a и b, и они выводятся с
помощью правил
A → a и B → b.
Индукционная гипотеза. Предположим, что утверждения 1) – 3), выпол-
няются для всех
x, таких что |x| = l, l ≤ k (k ≥ 1).
Индукционный переход. Покажем, что они истинны для l = k + 1.
1) Если #
a
x = #
b
x, то либо первый символ x есть a, либо он есть b.
Предположим, что
x = ax
1
, где |x
1
| = k . В этом случае #
b
x
1
= #
a
x
1
+ 1, и по
индукционной гипотезе существует вывод
B
x
1
, а тогда с помощью правила
S → aB можно построить вывод S aB ax
1
= x.
Случай x = bx
1
разбирается аналогично.
Для завершения доказательства подобным же образом должны быть
доказаны утверждения 2) и 3).
Определение 2.9. Грамматика G=(V
N
, V
T
, P, S) является грамматикой типа 3
или
регулярной грамматикой (rg — regular grammar), если каждое её правило
имеет вид
A → aB или A → a, где a∈ V
T
, A, B∈ V
N
.
Замечание 2.3. В гл. 3 будет определено абстрактное устройство, называемое
конечным автоматом, и показано, что языки, порождаемые грамматиками типа 3,
являются в точности теми множествами, которые распознаются (допускаются) этими
устройствами. Поэтому такой класс грамматик и языков часто называют (конечно-)
автоматными или просто автоматными.
Пример 2.4. Рассмотрим грамматику G = (V
N
, V
T
, P, S), где V
N
={S, A, B},
V
T
= {0, 1}, P = {S → 0A, S → 1B, S → 0, A → 0A, A → 0S, A → 1B, B → 1B,
B → 1, B → 0}.
Ясно, что
G — регулярная грамматика. Определить, какой язык порождает
данная грамматика и доказать это, предоставляем читателю.
Очевидно, что каждая регулярная грамматика — контекстно-свободна;
каждая контекстно-свободная грамматика — контекстно-зависима; каждая
контекстно-зависимая грамматика является грамматикой типа 0.
Каждому классу грамматик соответствует класс языков. Языку
приписывается тип грамматики, которой он порождается. Например,
контекстно-свободные грамматики (cfg) порождают контекстно-свободные
языки (cfl —
context-free language), контекстно-зависимые грамматики (csg)
порождают контекстно-зависимые языки (csl — context-sensitive language).
В соответствии с текущей практикой язык типа 3 или регулярный язык
часто называют
регулярным множеством (rs — regular set). Язык типа 0
называют
рекурсивно перечислимым множеством (res — recursively enumer-
able
set). Далее будет показано, что языки типа 0 соответствуют языкам,
которые интуитивно могут быть перечислены конечно описываемыми
процедурами.
*
⇒
*
⇒
*
⇒
*
⇒
⇒
*
⇒

Страницы