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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Поскольку МПА оказался в заключительной ситуации ),,(
0
BqB их входной
ленте порождена цепочка
m
L
∈
α
. Нетрудно видеть, что описанный МПА
никогда не может породить, например, цепочку
авcвв
=
β
, такую, что
m
L
∉
β
.
Другими словами, если автомат оказывается в ситуации
),,(
0
BqB , то на
входной ленте всегда записана правильная цепочка данного языка.
Очевидно, что в общем случае порождающий МПА не является
детерминированным. Недетерминированность автомата проявляется при
порождении подцепочки х слова
α
. При порождении подцепочки х
-1
, автомат
становится детерминированным.
Нетрудно показать, что в общем случае для любой КС-грамматики G
можно построить МПА, допускающий (порождающий) язык L(Q), и
наоборот, язык, допускаемый (порождаемый) МПА является КС-языком.
Поэтому справедливо утверждение о том, что класс языков, допускаемых
(порождаемых) МПА, совпадает с классом КС-языков.
3.4. Автоматные
грамматики и языки
Автоматные грамматики ***** КС-грамматик. Для задания А-
грамматики ****************
Для любой левосторонней грамматики можно построить эквивалентную
правостороннюю и наоборот. Любая А-грамматика порождает автоматный
язык (А-язык), быть может пустой.
Пример 3.7. Пусть задана правосторонняя грамматика *****,
},{
21
AAV
A
= , },{
21
xxV
T
= .
)4(
)3(
)2(
)1(
:
22
222
211
111
xA
AxA
AxA
AxA
R
→
→
→
→
.
Грамматика G
n
задает язык, состоящий из всевозможных слов, которые
начинаются последовательностью из х**** *** последовательностью из х
2
,

Страницы