Теория алгоритмов и формальных языков. Мелихов А.Н - 16 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

2) выделенное непустое слово S - аксиому )( BAS U
∈
;
3) конечное множество правил вывода, задаваемых ориентированными
подстановками.
В простейшем случае ориентированная подстановка имеет вид:
BA → ,
где А и В - слова в алфавите
ВА U . Подстановка такого вида является
бесконтекстной, носит название полутуэвской и означает, что слово А
заменяется словом В. Ясно, что обратная подстановка
АВ →
также является
полутуэвской. Если имеются одновременно прямая и обратная подстановки,
то их можно заменить одной неориентированной (туэвской) подстановкой
А∼В. При наличии контекста полутуэвская подстановка имеет вид
PBQPAQ → , где Р и Q - некоторые (возможно пустые) слова в том же
алфавите.
Ориентированная подстановка вида
PBAP → называется нормальной.
Обратная подстановка
APPB →
называется антинормальной. Совокупность
нормальной и антинормальной подстановок, т.е. неориентированная
подстановка АР∼РВ, называется постовской.
Таким образом, в зависимости от типа используемых подстановок
можно рассматривать следующие частные виды комбинаторных систем:
полутуэвская, туэвская, нормальная и постовская.
Пример 1.1. Пусть задана полутуэвская система, в которой
},{ ваА
=
-
основной алфавит,
}{sB = - вспомогательный алфавит, состоящий из одной
буквы - аксиомы S, и три подстановки: 1)
авs → ; 2) asвB → ; 3) вsas → .
Множество всех формул, выводимых в этой системе можно представить в
виде бесконечного ориентированного графа, каждая вершина которого
помечена некоторым словом из алфавита
ВА U , а дуги помечаются номером
используемой подстановки. Фрагмент этого графа показан на рис. 1.1.

Страницы