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

UptoLike

ВУЗ: 

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

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

Рубрика: 

т.е. },{)(
21
nm
n
xxGL = , где ***. Например, слово )(
2
2
4
1221111
xxxxxxxx может быть
получено выводом:
→→→→→→
221111211111111
)11
111
)1
11
)1
1
AxxxxxhxxxxAxxxAxxAxA
221111
xxxxxx→ . Этот же язык может быть получен левосторонней грамматикой
},,,{
1
RAVVG
TAA
= , где },{
21
AAV
A
= , },{
21
xxV
T
=
с правилами вывода А вида:
)4(
)3(
)2(
)1(
:
12
122
221
211
xA
xAA
xAA
xAA
R
→
→
→
→
.
Действительно, цепочка
2
2
4
1
xx может быть получена в грамматике G
А
следующим выводом:
)4(
221112
)3(
22112
)3(
2212
)3(
222
)2(
21
)1(
1
→→→→→→ xxxxxAxxxxAxxxAxxAxAA
221111
)4(
xxxxxx→ . Поэтому )()(
An
GLGL = .
Любой конечный язык является А-языком. Действительно, множество,
содержащее n слов
},...,{
21 n
α
α
α
, где слово
k
iiii
xxx ,...,
21
=
α
, может быть описано
следующей А-грамматикой с правилами вывода вида:
11
1 ii
AхА → ;
211
iii
AхА → ;
…,
12
,,
−−
→
ii
kiki
xA ;
ii
kiki
xA
,,
1
→
−
, где ni
≤
≤
1 .
Важной особенностью А-грамматики является возможность
представления их с помощью конечных графов. По графу грамматики легко
отыскивается вывод нужного слова. Для представления грамматики в виде
графа необходимо преобразовать ее к виду так называемой
модифицированной грамматики. Пусть имеется А-грамматика
},,,{
1
RAVVG
TA
= . Дополним алфавит V
А
символом k (k - концевой символ).
Получим
}{kVV
AA
U=
′
. Все терминальные правила вывода А
i
x
j
заменим
правилами
kxA
ji
→ ,
λ
→k
. Получим новое множество правил и
модифицированную А-грамматику
},,,{
1
RAVVG
TA
′
′
=
′
. Каждому символу из
A
V
′
сопоставим вершину графа. Каждому правилу вывода
kji
AxA →
сопоставим
дугу из вершины A
i
в вершину A
k
и пометим ее буквой x
j
. Каждому правилу
вывода
kxA
ji
→ сопоставим дугу, ведущую из A
i
в k и помеченную буквой x
j
.
Любой вывод слова в А-грамматике соответствует пути в графе грамматики,

Страницы