Всегда ли наборы до и после для контекстно-свободных грамматик всегда контекстно-свободны?

14

Пусть G - не зависящая от контекста грамматика. Строка терминалов и нетерминалов из G называется быть сентенциальная формой из G , если вы можете получить его путем применения постановки G нуля или более раз для начального символа S . Пусть SF(G) множество пропозициональных форм G .

Пусть αSF(G) , и пусть β будет подстрока α - мы называем β на фрагмент из SF(G) . Теперь давай

Before(β)={γ | δ.γβδSF(G)}

и

After(β)={δ | γ.γβδSF(G)} .

А Before(β) и After(β) контекстно-свободных языков? Что если G однозначно? Если G однозначно, описываются ли Before(β) и After(β) также однозначным контекстно-свободным языком?

Это продолжение моего более раннего вопроса , после того как более ранняя попытка облегчить мой вопрос не удалась. Отрицательный ответ сделает очень сложным вопрос, над которым я работаю.

Алекс тен Бринк
источник

Ответы:

8

Давайте сначала почувствуем и После ( β ) . Рассмотрим дерево деривации, которое содержит β ; «содержит» здесь означает, что вы можете вырезать поддеревья, так что β является подсловом фронта дерева. Тогда набор до (после) - это все потенциальные фронты части дерева слева (справа) от β :Before(β)After(β)βββ

дерево с наборами до и после
[ источник ]

Таким образом, мы должны построить грамматику для горизонтально выровненной (вертикально выровненной) части дерева. Это кажется достаточно простым, поскольку у нас уже есть грамматика для всего дерева; мы просто должны убедиться, что все формы предложения являются словами (изменить алфавиты), отфильтровать те, которые не содержат (это обычное свойство, так как β фиксировано), и вырезать все после (до) β , включая β . Эта резка также должна быть возможной.ββββ


Теперь к формальному доказательству. Мы преобразуем грамматику, как изложено, и будем использовать свойства замыкания чтобы выполнять фильтрацию и вырезание, т.е. мы выполняем неконструктивное доказательство.CFL

Пусть бесконтекстная грамматика. Легко видеть, что SF ( G ) не зависит от контекста; построить G = ( N , T , δ , N S ) следующим образом:G=(N,T,δ,S)SF(G)G=(N,T,δ,NS)

  • N={NAAN}
  • T=NT
  • δ={α(A)α(β)Aβδ}{NAAAN}

с для всех т T и α ( ) = N для всех в N . Ясно, что L ( G ) = SF ( G ) ; следовательно, соответствующее закрытие префикса Pref ( SF ( G ) ) и закрытие суффикса Suff ( SF ( G ) ) также не зависят от контекста¹.α(t)=ttTα(A)=NAaNL(G)=SF(G)Pref(SF(G))Suff(SF(G))

Теперь для любого являются L ( β ( N T ) ) и L ( ( N T ) β ) регулярные языки. Так как C F L замкнут относительно пересечения и соотношения справа / слева с регулярными языками, мы получаемβ(NT)L(β(NT))L((NT)β)CFL

Before(β)=(Pref(SF(G))  L((NT)β))/βCFL

и

.After(β)=(Suff(SF(G))  L(β(NT)))βCFL


¹ является закрытым под правым (и слева) фактор ; Pref ( L ) = L / Σ и аналогично префиксу выхода Suff, соответственно. закрытие суффикса.CFLPref(L)=L/ΣSuff

Рафаэль
источник
Я начал писать ответ и понял, что мои доказательства такие же, как и у вас. Я бы сказал так (сжатый , чтобы соответствовать здесь): сформировать грамматику путем добавления нового терминала А (а метапеременную) для каждого нетерминала A и производство A . Тогда формой предложения G являются слова, распознаваемые G, которые состоят из мета-переменных. Это пересечение CFG с обычным языком и, следовательно, является регулярным. Набор префиксов CFG - это CFG (возьмите КПК и сделайте каждое состояние окончательным). B e f o r e ( γ ) =GA^AAA^GG есть снова CFG. Before(γ)={γγβL(Prefix(G^))}
Жиль "ТАК ... перестать быть злым"
1
@ Жиль, три комментария по этому поводу: 1) Формы предложения обычно (правильно) содержат язык. 2) «сделать каждый штат окончательным» - это не сработает; вы также будете принимать префиксы не-слов. 3) Последний шаг «обрезания» суффикса кажется сложным, чтобы стать строгим. : / У вас есть строгое, но более компактное доказательство, чем у меня?
Рафаэль
1) не имеет значения (измените чтобы иметь или не иметь нетерминал для каждого терминала). 2) Ой, я слишком много отсекаю: сделайте каждое состояние, которое может достичь конечного состояния, финальным. 3) Делайте это по одному терминалу b одновременно; в КПК отметьте состояния, из которых можно достичь конечного состояния, вместо этого выбрав b как конечное. Да, потребовалось бы больше расширения, чтобы сделать это строгим. Gbb
Жиль "ТАК - перестань быть злым"
9

Да, и После ( β ) являются контекстно-свободными языками. Вот как я это докажу. Во-первых, лемма (которая суть). Если L является CF, то:Before(β)After(β)L

Before(L,β)={γ | δ.γβδL}

и

After(L,β)={γ | δ.δβγL}

являются CF.

Доказательство? Для создайте недетерминированный конечный датчик T β, который сканирует строку, выводя каждый входной символ, который он видит, и одновременно ищет недетерминированный β . Всякий раз, когда T β видит первый символ β, он недетерминированно разветвляется и прекращает вывод символов до тех пор, пока он либо не завершит просмотр β, либо не увидит, видит символ, отклоняющийся от β , и останавливается в любом случае. Если T β видит βBefore(L,β)TββTββββTββв полном объеме, он принимает после остановки, что является единственным способом, которым он принимает. Если он видит отклонение от , он отклоняет.β

Лемма может быть воспроизведена для обработки случаев, когда может перекрываться с самим собой (например, a b a b - продолжайте искать β даже в процессе сканирования на предмет предшествующего β ) или встречаться несколько раз (фактически, исходный недетерминированный разветвление уже справляется с этим). βababββ

Tβ(L)=Before(L,β)Before(L,β)

After(L,β)Before(L,β)

After(L,β)=rev(Before(rev(L),rev(β)))

After(L,β), since the transducer for that is simpler to describe and verify -- it outputs the empty string while looking for a β. When it finds β it forks non-deterministically, one fork continuing to look for further copies of β, the other fork copying all subsequent characters verbatim from input to output, accepting all the while.

What remains is to make this work for sentential forms as well as CFLs. But that is pretty straightforward, since the language of sentential forms of a CFG is itself a CFL. You can show that by replacing every non-terminal X throughout G by say X, declaring X to be a terminal, and adding all productions XX to the grammar.

I'll have to think about your question on unambiguity.

David Lewis
источник