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

UptoLike

ВУЗ: 

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

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

Рубрика: 

18
Правила подстановки. Это выражения вида «X → Y», «Х вместо Y», где Х и
Y – цепочки, содержащие любые терминальные или нетерминальные символы.
Для описания собственно процесса порождения, т. е. как грамматика применя-
ется, необходимо введение таких понятий, как непосредственная выводимость;
язык, порожденный грамматикой.
Непосредственная выводимость. Если имеются цепочки Х и Y, которые
можно представить в виде X = Z
1
a Z
2
и Y = Z
1
b Z
2
, где a → b – одно из правил
грамматики G, то говорят, что цепочка Y непосредственно выводима из цепочки Х в
грамматике G. Другими словами, цепочка Х может быть переработана в цепочку Y за
один шаг применением одной подстановки: Х получается из Y подстановкой b на ме-
сто некоторого вхождения цепочки а. Это обозначается как Х / G = Y.
Выводимость. Если имеется последовательность цепочек Х
0
, Х
1
, ..., Х
n
, в ко-
торой каждая следующая цепочка непосредственно выводима из предыдущей, то це-
почка Х
n
выводима из цепочки Х
0
. Последовательность цепочек Х
0
, Х
1
, ..., Х
n
называ-
ется выводом Х
n
из Х
0
– в грамматике G.
Существенно, что порождающая грамматика не есть алгоритм, поскольку пра-
вила подстановки представляют собой не последовательность предписаний, а сово-
купность решений. Это означает, что, во-первых, правило вида a → b понимается в
грамматике как «а можно заменить на b» (но можно и не заменять); в алгоритме же
a → b означало бы «а следует заменить на b» (нельзя не заменять); во-вторых, поря-
док применения правил в грамматике произволен: любое правило, в принципе, раз-
решается применять после любого.
Язык, порожденный грамматикой. Совокупность всех терминальных цепо-
чек, т. е. цепочек, состоящих только из терминальных символов, выводимых из на-
чального символа в грамматике G, называется языком, порожденным грамматикой G,
и обозначается L(G).
Следовательно, применение грамматики – это построение полных выводов, по-
следние цепочки которых и образуют язык, порожденный грамматикой.
Две различные грамматики могут порождать один и тот же язык, т. е. одно и то
же множество терминальных цепочек. Такие грамматики называются эквивалент-
ными грамматиками.
1.5. Автоматы и формальные языки
1.5.1. Понятие об информации и ее преобразованиях
Понятие информации принадлежит к числу важнейших понятий современной
науки. Важность этого понятия обуславливается его всеобщностью: с понятием ин-
формации мы сталкиваемся при изучении любого явления, происходящего в природе
или обществе.
Существуют два различных подхода к изучению явлений с информационной
точки зрения: непрерывный и дискретный. При непрерывном подходе все изучаемые
явления рассматриваются как переменные векторные поля. Задание информации со-
стоит в выборе какого-либо определенного (переменного) поля из фиксированной за-

Страницы