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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Пусть задана А- грамматика ),,,( RAVVG
TA
=
и пусть )(GL - язык порождаемый ею.
Построим КА, допускающий слова языка )(GL . Каждому символу
A
VA ∈
1
сопоставляем
Qq
i
∈ . Кроме этого, для автомата введем начальное состояние
0
q , котороене
соответствует никакому нетерминальному символу грамматики G вида
ji
xA →
сопоставим команду вида
(
)
ε
qxq
jk
→,, которая соответствует переходу автомата из
состояния
k
q в
ε
q по букве
j
x . Заключительной командой КА будет
()
01
, qq →
ε
,
переводящая автомат из последнего текущего состояния (соответствующего аксиоме
1
A
грамматики G) в начальное состояние
0
q по пробелу
ε
. Таким образом, по грамматике G
построен конечный автомат, заданный описанным множеством команд.
Нетрудно показать, что по заданному КА, допускающему L(G), можно однозначно
построить правила вывода A- грамматики G.
Пример 3.8. Для грамматики
A
G , порождающей
{
}
nm
A
xxGL
21
,)( = , построим
множество команд, описывающих функционирование конечного автомата A,
допускающего язык
)(
A
GL
. Грамматика
A
G
имеет одно терминальное
12
xA →
. Вводим
начальное состояние Qq ,,
0
ε
и записываем команду
210
),( qxq → , сопоставляем символу
2
A состояние Qq ∈
2
. Далее по правилу
211
xAA → записываем команду
()
112
, qxq → ,
сопоставляем
1
A состоянию
1
q . Затем по правилам вывода (2) и (3) грамматики
A
G
записываем команды
122
),( qxq → и
(
)
212
, qxq → соответственно. После этого записываем
заключительную команду
()
01
, qq →
ε
. Таким образом, автомат A, допускающий язык
)(
A
GL
, задается набором команд:
210
),( qxq → ;
122
),( qxq → ;
()
01
, qq →
ε
.
()
121
, qxq → ;
()
212
, qxq →
Для слова d=
1
x
1
x
1
x
1
x
2
x
2
x последовательность вычислений (по аналогии с машиной
Тьюринга) автомата А имеет вид
0
q
1
x
1
x
1
x
1
x
2
x
2
x
1
x
2
q
1
x
1
x
1
x
2
x
2
x
1
x
1
x
2
q
1
x
1
x
2
x
2
x
1
x
1
x
1
x
1
x
2
x
2
x
1
x
1
x
1
x
2
q
1
x
2
x
2
x
1
x
1
x
1
x
1
x
2
q
2
x
2
x
1
x
1
x
1
x
1
x
2
x
1
q
2
x
ε
1
q
1
x
1
x
1
x
1
x
2
x
2
x
ε
0
q
Поскольку автомат оказался в ситуации
(
)
ε
,
0
q , то слово d допустимо автоматом A. Легко
проверить, что любое слово языка
)(
A
GL
допустимо автоматом А.
Заметим, что описанным способом может быть построена КА, допускающий
любой A- язык, порождаемый левосторонней грамматикой. Поэтому такие КА можно
назвать левосторонними автоматами. Для правосторонних грамматик и языков, или
порождаемых, необходимо ввести правосторонние КА. Входная лента такого КА
ограничена справа, неограниченна слева и сдвигается слева направо. Входное слово на
ленте читается справа
налево в отличие от общепринятого направления чтения.
Для правосторонней грамматики
n
G , используя описанную ниже методику, можно
построить правосторонний КА
ε
, допускающий язык )(
n
GL , который имеет следующию
последовательность команд:

Страницы