ВУЗ:
Составители:
Введем некоторые определения. Говорят, что цепочка
ω
1
непосредственно выводима из цепочки
ω
, если
21121
ξ
ω
ξ
ωξ
ξ
→ , где
}{,
21 TA
VV U∈
ξ
ξ
. Говорят, что цепочка
ω
N
выводима из цепочки
ω
0
, если
существует последовательность непосредственных выводов:
1+
→
ii
ω
ω
,
1,0 −= ni . В этом случае будем записывать
N
G
ω
ω
→
0
.
Если
S=
0
ω
, то говорят, что цепочка
ω
N
выводима из аксиомы.
Терминальную цепочку, т.е. цепочку символов терминального
алфавита, выводимую из некоторого нетерминального символа, будем
называть терминальным порождением этого символа. Особо подчеркнем, что
множество всех терминальных цепочек грамматики G, выводимых из
аксиомы S, образует язык L(G), порождаемый этой грамматикой.
Одной из основных проблем, связанных с использованием
грамматик
является проблема распознавания. Эта проблема разрешима, если существует
такой алгоритм, который за конечное число шагов дает ответ на вопрос:
входит ли цепочка основных символов языка в язык, порождаемый этой
грамматикой? Если число шагов такого алгоритма можно подсчитать до его
выполнения (такой алгоритм называется эффективным), то язык называется
легко распознаваемым.
Длиной цепочки l(
ω
) называется число ее символов. Если 0)(
=
ω
l , то
мы имеем пустую цепочку, которая обозначается
λ
. Порождающая
грамматика называется неукорачивающей, если для всех ее правил
η
ξ
→
имеет место
)()(
η
ξ
ll ≤ .
Американским математиком Н. Хомским была предложена следующая
классификация порождающих грамматик.
1-й класс составляют грамматики непосредственных составляющих
(НС-грамматики). НС-грамматики - это неукорачивающие грамматики с
правилами вывода типа
2121
ηξ
ξ
ξ
ξ
→А , где
η
ξ
ξ
,,
21
- произвольные цепочки из
Страницы
- « первая
- ‹ предыдущая
- …
- 47
- 48
- 49
- 50
- 51
- …
- следующая ›
- последняя »
