Языки и трансляции. Мартыненко Б.К. - 67 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

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

Рубрика: 

66
Пример 4.6. Язык {(ab)
n
c
n
(dd)
*
| n ≥ 1} является ограниченным языком.
Здесь k =3, а w
1
= ab, w
2
= c, w
3
= d.
Определение 4.9. Говорят, что контекстно-свободная грамматика
G =(V
N
, V
T
, P, S) — неоднозначна, если в языке L(G) существует цепочка с
двумя или более различными левосторонними выводами.
Если все грамматики, порождающие некоторый контекстно-свободный
язык, неоднозначны, то говорят, что этот язык существенно неоднозначен.
Существенно неоднозначные контекстно-свободные языки существуют.
Классическим
примером такого языка является язык L ={a
i
b
j
c
k
| i = j или
j = k}. Основная причина, по которой язык L существенно неоднозначен,
состоит в том, что любая cfg, порождающая язык L, должна порождать те
цепочки, для которых i = j, при помощи процесса, который отличается от
процесса порождения тех цепочек, для которых j = k. Невозможно не
порождать некоторые из тех цепочек, для которых i = j = k, посредством
обоих процессов. Строгое доказательство этого факта весьма сложно (см.,
например, [1]).
Известно, что проблема распознавания существенной неоднозначности
КС-языков алгоритмически неразрешима.
Пример 4.7. Рассмотрим грамматику G из примера 4.1, которая имеет
следующие правила:
P =
{S → bA,
S → aB, A→ aS, A→ bAA, A → a, B→ bS, B→ aBB, B→ b}.
Цепочка aabbab выводится посредством двух разных левосторонних
выводов:
S ⇒ aB ⇒ aaBB ⇒ aabB ⇒ aabbS ⇒ aabbaB ⇒ aabbab,
S ⇒ aB ⇒ aaBB ⇒ aabSB ⇒ aabbAB ⇒ aabbaB ⇒ aabbab.
Следовательно, грамматика G — неоднозначная. Однако язык состоит из
цепочек, содержащих равное число букв a и b, и может быть порожден
однозначной грамматикой G
1
=({S, A, B}, {a, b}, P, S), где P состоит из правил
S → aBS, S → aB, S → bAS, S → bA, A → bAA, A → a, B → aBB, B → b.
Упражнения
I-4.1. Постройте алгоритм для определения, пуст ли язык, порождаемый
данной cfg. Заметим, что если грамматика порождает непустой язык, то, по
крайней мере, один нетерминал должен иметь правило, правая часть
которого
содержит только терминалы.
I-4.2. Даны две цепочки a
1
и a
2
и cfg G. Построить алгоритм для опреде-
ления:
I-4.3. Дана cfg G = (V
N
, V
T
, P, S), где V
N
= {E, T, F}, V
T
= {a, +,
*
, (,)}, S = E,
P = {(1) E → E + T, (2) E → T, (3) T → T
*
F, (4) T → F, (5) F → (E), (6) F → a}.
Построить эквивалентную cfg в нормальной форме Хомского.
12
*
?
G
aa⇒

Страницы