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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Если изобразить граф выводимых в данной системе формул, то можно
убедиться, что формула асв является неоднозначной, так как для нее
существует три вывода: 1)
асвasвass
421
→→→
, 2)
асвasвsвs
412
→→→
, 3)
асвasвs
43
→→ . Поэтому эта полутуэвская система является неоднозначной.
1.3. Соответствие между полутуэвской и нормальной системами
Пусть задана полутуэвская система П, состоящая из алфавита
},,{ сваА = , слова
АС ∈
- аксиомы и подстановок QPBQРА
ii
→ ,
mi
≤
≤
1
.
Добавим в алфавит А буквы со штрихами и получим алфавит
},,,,,{ свaсваB
′′′
= . Построим нормальную систему N, входящую в алфавит В,
ту же аксиому С, в следующие подстановки:
1) аРаР
′
→ , вРвР
′
→ , сРсР
′
→ ;
2)
РаРа →
′
, РвРв →
′
, РсРс →
′
;
3)
ii
РBРА → , mi ≤≤1 .
Заметим, что подстановки типов 1) и 2) позволяют переставлять некоторую
букву из начала слова в его конец, меняя при этом ее «штриховость» на
обратную. Например, применяя к слову ваав соответствующие подстановки,
можно получить циклический вывод:
21111
→
′′′′
→
′′′
→
′′
→
′
→ ваавааввававваавваав
вааввааввававваа
2222
→
′
→
′′
→
′′′
→ . Все слова в этой цепочке называются
сопряженными. Каждая совокупность сопряженных слов образует класс
эквивалентности. Заметим, что среди всех слов, сопряженных со словом А,
есть и А′. Поэтому подстановки 1) и 2) позволяют за несколько шагов
переставлять слова из начала в конец.
Все слова, имеющие форму РQ′ или Р
′
Q, где *, АQР
∈
, сопряженные со
словами из А* и только с ними, называются регулярными. В классе
эквивалентности, рассмотренном выше, не существует регулярных слов. А в
классе эквивалентности
→
′
′
→
′′′
→
′
′
′
′
→
′
′
→
′
→
′
→ ававаавваввавваававаавваавва

Страницы