Давайте сначала почувствуем и После ( β ) . Рассмотрим дерево деривации, которое содержит β ; «содержит» здесь означает, что вы можете вырезать поддеревья, так что β является подсловом фронта дерева. Тогда набор до (после) - это все потенциальные фронты части дерева слева (справа) от β :Before(β)After(β)βββ
[ источник ]
Таким образом, мы должны построить грамматику для горизонтально выровненной (вертикально выровненной) части дерева. Это кажется достаточно простым, поскольку у нас уже есть грамматика для всего дерева; мы просто должны убедиться, что все формы предложения являются словами (изменить алфавиты), отфильтровать те, которые не содержат (это обычное свойство, так как β фиксировано), и вырезать все после (до) β , включая β . Эта резка также должна быть возможной.ββββ
Теперь к формальному доказательству. Мы преобразуем грамматику, как изложено, и будем использовать свойства замыкания чтобы выполнять фильтрацию и вырезание, т.е. мы выполняем неконструктивное доказательство.CFL
Пусть бесконтекстная грамматика. Легко видеть, что SF ( G ) не зависит от контекста; построить G ′ = ( N ′ , T ′ , δ ′ , N S ) следующим образом:G=(N,T,δ,S)SF(G)G′=(N′,T′,δ′,NS)
- N′={NA∣A∈N}
- T′=N∪T
- δ′={α(A)→α(β)∣A→β∈δ}∪{NA→A∣A∈N}
с для всех т ∈ T и α ( ) = N для всех в ∈ N . Ясно, что L ( G ′ ) = SF ( G ) ; следовательно, соответствующее закрытие префикса Pref ( SF ( G ) ) и закрытие суффикса Suff ( SF ( G ) ) также не зависят от контекста¹.α(t)=tt∈Tα(A)=NAa∈NL(G′)=SF(G)Pref(SF(G))Suff(SF(G))
Теперь для любого являются L ( β ( N ∪ T ) ∗ ) и L ( ( N ∪ T ) ∗ β ) регулярные языки. Так как C F L замкнут относительно пересечения и соотношения справа / слева с регулярными языками, мы получаемβ∈(N∪T)∗L(β(N∪T)∗)L((N∪T)∗β)CFL
Before(β)=(Pref(SF(G)) ∩ L((N∪T)∗β))/β∈CFL
и
.After(β)=(Suff(SF(G)) ∩ L(β(N∪T)∗))∖β∈CFL
¹ является закрытым под правым (и слева) фактор ; Pref ( L ) = L / Σ ∗ и аналогично префиксу выхода Suff, соответственно. закрытие суффикса.CFLPref(L)=L/Σ∗Suff
Да, и После ( β ) являются контекстно-свободными языками. Вот как я это докажу. Во-первых, лемма (которая суть). Если L является CF, то:Before(β) After(β) L
и
являются CF.
Доказательство? Для создайте недетерминированный конечный датчик T β, который сканирует строку, выводя каждый входной символ, который он видит, и одновременно ищет недетерминированный β . Всякий раз, когда T β видит первый символ β, он недетерминированно разветвляется и прекращает вывод символов до тех пор, пока он либо не завершит просмотр β, либо не увидит, видит символ, отклоняющийся от β , и останавливается в любом случае. Если T β видит βBefore(L,β) Tβ β Tβ β β β Tβ β в полном объеме, он принимает после остановки, что является единственным способом, которым он принимает. Если он видит отклонение от , он отклоняет.β
Лемма может быть воспроизведена для обработки случаев, когда может перекрываться с самим собой (например, a b a b - продолжайте искать β даже в процессе сканирования на предмет предшествующего β ) или встречаться несколько раз (фактически, исходный недетерминированный разветвление уже справляется с этим).β abab β β
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-terminalX throughout G by say X′ , declaring X to be a terminal, and adding all productions X′→X to the grammar.
I'll have to think about your question on unambiguity.
источник