Как я могу доказать, что язык является контекстно-свободным, если я удалю один символ из его алфавита?

Предположим, что у нас есть язык L, не зависящий от контекста, и буква «а» среди прочих принадлежит его алфавиту. Как я могу доказать, что язык ERASEa(L), который удаляет все экземпляры символа 'a' в строках, созданных L (например, abbac -> bbc), по-прежнему не зависит от контекста? Заранее спасибо!


compiler-construction computation compiler-theory
person lone luttrell    schedule 27.05.2016    source источник
comment
Я предполагаю, что эта проблема связана с курсом, который вы проходите или изучаете самостоятельно. Трудно поверить, что в вашем учебнике нет хотя бы некоторых советов о том, как построить это доказательство, но достаточно легко найти ссылки в Интернете. Вы можете начать с википедии и следующего раздела. (Доказательство состоит в построении грамматики для нового языка путем изменения старой грамматики, а затем в доказательстве правильности построенной грамматики.)   -  person rici    schedule 27.05.2016

Ответы (1)


arrow_upward
0
arrow_downward

Мой подход заключается в том, что если L — контекстно-свободный язык, то существует некоторая грамматика G = (V, Σ, R, S). Набор терминалов V и начальный символ S остаются неизменными. Набор терминалов Σ становится Σ' = Σ - 'a'. Наконец, набор отношений производственных правил R = V -> (V ∪ )* модифицируется таким образом, что R' = V -> (V ∪ ')*, где правила в R' — это те же правила в R с удаленным 'a' . Поскольку G' = (V, ', R', S) является допустимым CFG, L без 'a' является контекстно-свободным языком.

person robot1208    schedule 05.07.2016