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

UptoLike

ВУЗ: 

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

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

Рубрика: 

11
цепочке Х. Более интересными, с точки зрения теории формальных грамматик, явля-
ются соотношения, в которых введено направление.
В этом случае их называют полусоотношениями Туэ или продукциями и обо-
значают следующим образом:
(Р
1
→ Q
1
), (P
2
→Q
2
), ..., (P
n
→ Q
n
).
В том случае, когда имеется набор продукций, говорят, что цепочка Y непо-
средственно порождается из цепочки Х, и обозначается как Х ⇒ Y, если существуют
такие цепочки U и V, что
X = U P
i
V, Y = U Q
i
V,
а (Р
i
→ Q
i
) – продукция из данного набора.
Говорят также, что Х порождает Y.
Если существует последовательность цепочек Х
0
, Х
1
, ..., Х
n
такая, что для каж-
дого i = 1, 2, ..., n
Х
i-1
⇒ X
i
,
то говорят, что Х
n
порождается из Х
0
(Х
0
порождает Х
n
), и обозначают как Х
0
⇒
*
X
n.
.
Грамматики Хомского соответствуют формальным комбинаторным схемам,
являющимся полусистемами Туэ, в основу которых положены полусоотношения Туэ
(продукции).
1.3. Классификация языков по Хомскому
Теория формальных языков (формальных грамматик) занимается описанием,
распознаванием и переработкой языков. Описание любого языка должно быть конеч-
ным, хотя сам язык может содержать бесконечное множество цепочек. Полезно иметь
возможность описания отдельных типов языков, имеющих те или иные свойства, т. е.
иметь различные типы конечных описаний.
Предположим, что имеется некоторый класс языков L, который задается опре-
деленным типом описаний. Теория формальных языков позволяет ответить на ряд во-
просов, возникающих во многих прикладных задачах, в которых используются авто-
матно-лингвистические модели. Например, могут ли языки из класса L распознавать-
ся быстро и просто; принадлежит ли данный язык классу L и т. д. Важной проблемой
является построение алгоритмов, которые давали бы ответы на определенные вопро-
сы о языках из класса L, например: «Принадлежит цепочка Х языку L или не
принадлежит?»
Существуют два основных способа описания отдельных классов языков. Пер-
вый из них основан на ограничениях, которые налагаются на систему полусоотноше-
ний Туэ (продукций), на базе которых определяются грамматики как механизмы,
порождающие цепочки символов. Другим способом является определение языка в
терминах множества цепочек, с помощью некоторого распознающего устройства.
Такие устройства будем называть автоматами (автоматами-распознавателями).
Н. Хомский определил четыре типа грамматик, на основе которых оценивают-
ся возможности других способов описания языков.
Пусть алфавит символов (непустое конечное множество), из которых строятся
цепочки языка L, представляет собой алфавит терминальных символов V
Т
. Очевидно,
что L ≤ V
Т
*.

Страницы