Синтез цифровых автоматов. Захаров Н.Г - 13 стр.

UptoLike

ВУЗ: 

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

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

Рубрика: 

12
Определение формальной грамматики требует наличия еще одного алфавита
V
N
– непустого конечного множества нетерминальных символов (V
N
∧ V
Т
= 0). Объе-
динение этих алфавитов назовем словарем формального языка L:
V = V
N
∨ V
Т
.
Условимся обозначать элементы алфавита V
Т
строчными латинскими буквами,
элементы множества V
N
– прописными латинскими буквами, элементы словаря V*
(цепочки символов словаря) – греческими буквами.
Определим также множество упорядоченных пар (полутуэвских соотношений)
следующим образом:
П = {(α, β) | α ∈ V* V
N
V* ∧ β ∈ V
+
}.
Каждая пара (α, β) называется продукцией и обозначается как α → β.
Заметим, что β является элементом усеченной итерации словаря, поэтому среди
продукций нет пар вида α → ε, где ε – пустая цепочка.
Формальная грамматика G – это совокупность четырех объектов:
G = (V
T
, V
N
, P, S),
где Р – непустое конечное подмножество П, а S ∈ V
N
- начальный символ.
Типы грамматик по Хомскому обозначают: тип 0, тип 1, тип 2 и тип 3. Соответ-
ствующий тип грамматики определяется теми ограничениями, которые налагаются
на продукцию Р.
Если таких ограничений нет, грамматика принадлежит к типу 0.
Единственное ограничение, налагаемое на длину цепочек α и β:
| α | ≤ | β |,
относит грамматики к типу 1. Такие грамматики также называют контекстно-зависимыми,
то есть грамматиками непосредственных составляющих (НС-грамматиками).
В том случае, когда цепочка α состоит из одного символа, т. е. α ∈ V
N
, грамматики
относят к типу 2. В этом случае их называют бесконтекстными (контекстно-
свободными или КС-грамматиками).
Наконец, регулярными грамматиками (типа 3) называют такие, для которых
α ∈ V
N
, а β ∈ V
Т
V
N
, либо β ∈ V
Т
. Иными словами, правые части продукций регу-
лярных грамматик состоят либо из одного терминального и одного нетерминального
символов, либо из одного терминального символа.
Языком L(G), порождаемым грамматикой G, будем называть множество цепо-
чек α ∈ V
Т
, каждая из которых порождается из начального символа S в смысле полу-
туэвских соотношений Р данной грамматики. Другими словами,
L(G) = {α | α ∈ V
T
* ∧ S ⇒ *α}.
Нетрудно видеть, что каждая регулярная грамматика является бесконтекстной,
а каждая бесконтекстная грамматика является контекстно-зависимой. В свою очередь,
каждая контекстно-зависимая грамматика – это грамматика типа 0. Обратное утвер-
ждение неверно. Очевидно, что имеется некоторая иерархия грамматик, которой со-
ответствует иерархия формальных языков, каждый из них может быть порожден не-
которой формальной грамматикой. При этом тип языка соответствует типу той грам-
матики, с помощью которой он может быть порожден.
С другой стороны, типы языков могут быть определены типами абстрактных
распознающих устройств (автоматов). При этом язык определяется как множество
цепочек, допускаемых распознающим устройством определенного типа. На рис. 1.1

Страницы