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

UptoLike

ВУЗ: 

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

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

Рубрика: 

системе П - это слово
12
PАР
i
. Из сделанного предположения следует, что
слово
12
PАР
i
является формулой в системе П. Однако
12
PАР
i
сопряжено со
словом
i
ВРР
′′
21
, которое может быть получено с помощью подстановки 3) из
слова
21
PPА
i
′
. Очевидно, что слово
i
ВРР
′
′
21
является регулярным. Тем самым
теорема доказана.
Пример 1.4. Пусть дана полутуэвская система с алфавитом
},,{ сваА = ,
аксиомой которой служит слово
асвС
=
, и подстановкой РасвQРсQ → , где,
очевидно,
аР =
, вQ = . Эта система является моногенной и порождает
формулы типа
nn
cвa , где ,...2,1
=
n . Построим соответствующую ей
нормальную систему. Ясно, что эта система имеет алфавит
},,,,,{ свaсваB
′
′
′
= ,
аксиому
аcвC
′
= и подстановки
1)
аРаР
′
→
,
вРвР
′
→
,
сРсР
′
→
;
2)
РаРа →
′
, РвРв →
′
, РсРс →
′
;
3)
вcaРQРсQ
′′′′
→
′
.
Очевидно, что аксиома сва′ принадлежит классу эквивалентности
654321
асвсававсвсасавасв →
′
→
′′
→
′′′
→
′′
→
′
. Применяя к аксиоме подстановку 3),
получим формулу ва′а′с′в′, порождающую следующий класс
эквивалентности:
.
1098
7654321
саавваасвваасвв
аасвваасвваасввааввсаввсаввааавсаав
′′′
→
′
→
′
→
→→
′
→
′
′
→
′
′
′
→
′′′′
→
′′′′′
→
′′′′
Подстановка типа 3) может быть применена в этом классе только к слову
аасвв
′′
, в результате которой порождается слово всаавв
′′
′
′
и новый класс
эквивалентности и так далее.
Граф, представляющий множество всех выводимых формул в обеих
системах, показан на рис. 1.3.

Страницы