Контекстно-свободные языки

olish

Сейчас вот читаю, наткнулся на теорему, доказательство которой кажется мне подозрительным

Рассмотрим в качестве грамматики G (ведь доказательство не предъявляет к ней никаких требований, просто заявляет, что она существует по определению) следующую:
G = ({S, A}, {a}, {S->A, A->e, A->a}, S)
В этому случае к правилу "S->A" первый пункт доказательства применить невозможно, т.к. он требует в правой части наличия хотя бы alpha_0, из которого не должна выводиться пустая строка. В правиле "S->A" справа нет ничего, что можно было бы взять на роль alpha_0, таким образом это правило не будет принято во внимание.
В итоге P' будет содержать правила {S'->S, S'->e, A->a}, и из него не будет выводиться S' => a, хотя из исходной грамматики выводилось.
В доказательстве действительно ошибка, или я не так понял?
Есть предположение, что если вычеркнуть то, что я подчеркнул красным, то доказательство будет верным (в данном случае можно будет брать в качестве alpha_0 и alpha_1 пустые строки).

vsjshnikova

Сорри, фигню написал до этого.
Если просто убрать, то не получится
Там надо написать, что либо из [math]$\alpha_i$[/math] не выводится e, либо само [math]$\alpha_i$[/math] пустое.

olish

А зачем вообще здесь ограничение на alpha_i? Чем в доказательстве помешает случай, если из alpha_i будет выводиться пустая строка?

vsjshnikova

А зачем вообще здесь ограничение на alpha_i? Чем в доказательстве помешает случай, если из alpha_i будет выводиться пустая строка?
S->ABC, A->e, A->a, B->e, B->b, C->e, C->c
берем \alpha_0 = A, B_1 = B, \alpha_1 = C
получаем S->AC, S->ABC
при этом правил A->e, B->e, C->e у нас в результирующей грамматике не будет (по определению неукорачивающей грамматики так что строку bc, например, мы вывести не сможем.

olish

С этим согласен, но если правую часть какого-то правила можно привести к такому виду несколькими способами, то нужно рассматривать все, разве не так?
В вашем примере для правой части правила "S->ABC" нужно будет рассматривать разложения:
\alpha_0 = ABC
\alpha_0 = A, B_1 = B, \alpha_1 = C (то, что вы указали)
\alpha_0 = e; B_1 = A, \alpha_1 = e; B_2 = B; \alpha_2 = e; B_3 = C; \alpha_3 = e
и т.д. (всего возможно 8 разложений)
И для каждого разложения добавлять в P' соответствующие правила (будет некоторое излишество, но не страшно, это же теоретическое доказательство)
И неоднозначность разложения возникла НЕ из-за разрешения из alpha_j выводить пустую строку, неоднозначность была изначально.
Покажу на примере:
S->aAaBa, A->e, B->e
берем \alpha_0 = aAa, B_1 = B, \alpha_1 = a
а можно было \alpha_0 = a, B_1 = A, \alpha_1 = a, B_2 = B, \alpha_2 = a
*Возможно*, они имели в виду, что "alpha_j не должно содержать нетерминалов, из которых выводима пустая строка", тогда разложение было бы однозначным.

vsjshnikova

Согласен.
В таком случае лучше это вообще переформулировать.
Например, так: Для каждого нетерминала A, из которого выводится пустая строка, заменим все правила вида X->uAv на пары X->uAv, X->uv, а затем уберем все правила X->e и отдельно обработаем S.
Оставить комментарий
Имя или ник:
Комментарий: