Czy zestawy przed i po dla gramatyk bezkontekstowych zawsze są pozbawione kontekstu?

14

Niech $G$ będzie gramatyką bezkontekstową. Łańcuch zacisków i nieterminali z $G$ mówi się zdań tworzą z $G$ , czy można go otrzymać stosując produkcje $G$ zero lub więcej razy symbolu startu $S$ . Niech $\operatorname{SF}(G)$ będzie zbiorem form zdaniowych $G$ .

Niech $\alpha \in \operatorname{SF}(G)$ i pozwolić $\beta$ być podłańcuchem $\alpha$ - nazywamy $\beta$ się fragment o $\operatorname{SF}(G)$ . Teraz pozwól

$\operatorname{Before}(\beta) = \{ \gamma \ |\ \exists \delta . \gamma \beta \delta \in \operatorname{SF}(G) \}$

i

$\operatorname{After}(\beta) = \{ \delta \ |\ \exists \gamma . \gamma \beta \delta \in \operatorname{SF}(G) \}$ .

Czy języki $\operatorname{Before}(\beta)$ i $\operatorname{After}(\beta)$ bezkontekstowe? Co jeśli $G$ jest jednoznaczny? Jeśli $G$ jest jednoznaczne, czy $\operatorname{Before}(\beta)$ i $\operatorname{After}(\beta)$ również opisać jednoznaczny język bezkontekstowy?

Jest to kontynuacja mojego wcześniejszego pytania , po nieudanej próbie ułatwienia odpowiedzi na moje pytanie. Odpowiedź negatywna sprawi, że pytanie, na które ciężko pracuję, będzie bardzo trudne.

— Alex ten Brink
źródło

8

Pozwól nam uzyskać poczucie dla i w pierwszej kolejności. Rozważ drzewo pochodnych, które zawiera ; „zawiera” oznacza tutaj, że możesz odciąć poddrzewa, tak aby było podsłowem frontu drzewa. Następnie, przed (po) zestawem są wszystkie potencjalne fronty części drzewa po lewej (prawej) stronie : $\operatorname{Before}(\beta)$ $\operatorname{After}(\beta)$ $\beta$ $\beta$ $\beta$

tree with before and after sets
^{[ źródło ]}

Musimy więc zbudować gramatykę dla wyłożonej poziomo (pionowo) części drzewa. Wydaje się to dość łatwe, ponieważ mamy już gramatykę dla całego drzewa; musimy tylko upewnić się, że wszystkie sentymentalne formy są słowami (zmienić alfabety), odfiltrować te, które nie zawierają (co jest normalną właściwością, ponieważ jest ustalone) i odciąć wszystko po (przed) , w tym . To cięcie powinno być również możliwe. $\beta$ $\beta$ $\beta$ $\beta$

Teraz do formalnego dowodu. Zmienimy gramatykę zgodnie z przedstawionymi rysunkami i wykorzystamy właściwości zamykające do filtrowania i wycinania, tzn. Wykonujemy dowód niekonstruktywny. $\mathrm{CFL}$

Niech gramatyka bezkontekstowa. Łatwo zauważyć, że jest pozbawiony kontekstu; konstruuj następujący sposób: $G = (N, T, \delta, S)$ $\operatorname{SF}(G)$ $G'=(N',T',\delta',N_S)$

$N' = \{N_A \mid A \in N\}$
$T' = N \cup T$
$\delta' = \{\alpha(A) \to \alpha(\beta)\mid A\to\beta \in \delta \} \cup \{N_A \to A \mid A\in N\}$

z dla wszystkich i dla każdego . Oczywiste jest, że ; dlatego też odpowiednie prefiks i sufiks są pozbawione kontekstu¹. $\alpha(t)=t$ $t \in T$ $\alpha(A)=N_A$ $a\in N$ $\mathcal{L}(G')=\operatorname{SF}(G)$ $\operatorname{Pref}(\operatorname{SF}(G))$ $\operatorname{Suff}(\operatorname{SF}(G))$

Teraz, dla każdego są i zwykłe języki. Ponieważ jest zamknięte pod przecięciem i ilorazem prawo / lewo zwykłymi językami, otrzymujemy $\beta \in (N\cup T)^*$ $\mathcal{L}(\beta(N\cup T)^*)$ $\mathcal{L}((N\cup T)^*\beta)$ $\mathrm{CFL}$

$\qquad \displaystyle \operatorname{Before}(\beta) = (\operatorname{Pref}(\operatorname{SF}(G))\ \cap\ \mathcal{L}((N\cup T)^*\beta))\,/\,\beta \in \mathrm{CFL}$

and

$\qquad \displaystyle \operatorname{After}(\beta) = (\operatorname{Suff}(\operatorname{SF}(G))\ \cap\ \mathcal{L}(\beta(N\cup T)^*))\,\backslash\, \beta \in \mathrm{CFL}$ .

¹ $\mathrm{CFL}$ is closed under right (and left) quotient; $\operatorname{Pref}(L) = L / \Sigma^*$ and similar for $\operatorname{Suff}$ yield prefix resp. suffix closure.

— Raphael
źródło

I started to write an answer then realized my proof was the same as yours. I'd have put it this way (compressed to fit here): form a grammar

G^{'}

$G'$ by adding a new terminal

\hat{A}

$\hat A$ (a metavariable) for each non-terminal

A

$A$ and a production

A \to \hat{A}

$A\to\hat A$ . Then sentential forms of

G

$G$ are the words recognized by

G

$G$ that consist of metavariables. This is the intersection of a CFG with a regular language and thus is regular. The prefix set of a CFG is a CFG (take a PDA and make every state final).

B e f o r e (γ) = {γ ∣ γ β \in L (P r e f i x (\hat{G}))}

$\mathrm{Before}(\gamma) = \{\gamma \mid \gamma\beta\in L(\mathrm{Prefix}(\hat G))\}$ is again a CFG.

— Gilles 'SO- stop being evil'

1

@Gilles, three comments on that: 1) the sentential forms typically (properly) contain the language. 2) "make every state final" -- that won't work; you'll accept prefixes of non-words, too. 3) The last step of "cutting off" a suffix seems to be tricky to get rigorous. :/ Do you have a rigorous but more compact proof than mine?

— Raphael

1) doesn't matter (change

G

$G$ to have or not have a nonterminal for each terminal). 2) Oops, I cut off too much: make every state that can reach a final state final. 3) Do it one terminal

b

$b$ at a time; in the PDA, mark the states from which one can reach a final state by consuming

b

$b$ as final instead. Yes, it would take more expansion to make this rigorous.

— Gilles 'SO- stop being evil'

9

Yes, $\mbox{Before}(\beta)$ and $\mbox{After}(\beta)$ are context-free languages. Here's how I would prove it. First, a lemma (which is the crux). If $L$ is CF then:

$\mbox{Before}(L,\beta) = \{ \gamma \ |\ \exists \delta . \gamma \beta \delta \in L \}$

and

$\mbox{After}(L,\beta) = \{ \gamma \ |\ \exists \delta . \delta \beta \gamma \in L \}$

are CF.

Proof? For $\mbox{Before}(L,\beta)$ construct a non-deterministic finite-state transducer $T_{\beta}$ that scans a string, outputting every input symbol it sees and simultaneously searches non-deterministically for $\beta$ . Whenever $T_{\beta}$ sees the first symbol of $\beta$ it forks non-deterministically and ceases outputting symbols until either it finishes seeing $\beta$ or it sees sees a symbol that deviates from $\beta$ , stopping in either case. If $T_{\beta}$ sees $\beta$ in full, it accepts upon stopping, which is the only way it accepts. If it sees a deviation from $\beta$ , it rejects.

The lemma can be jiggered to handle cases where $\beta$ could overlap with itself (like $abab$ -- keep looking for $\beta$ even while in the midst of scanning for a prior $\beta$ ) or appears multiple times (actually, the original non-determinisic forking already handles that).

It's fairly clear that $T_\beta(L) = \mbox{Before}(L,\beta)$ , and since the CFLs are closed under finite-state transduction, $\mbox{Before}(L,\beta)$ is therefore CF.

A similar argument goes for $\mbox{After}(L,\beta)$ , or it could be done with string reversals from $\mbox{Before}(L,\beta)$ , CFLs also being closed under reversal:

$\mbox{After}(L,\beta) = \mbox{rev}(\mbox{Before}(\mbox{rev}(L),\mbox{rev}(\beta)))$

Actually, now that I see the reversal argument, it would be even easier to start with $\mbox{After}(L,\beta)$ , since the transducer for that is simpler to describe and verify -- it outputs the empty string while looking for a $\beta$ . When it finds $\beta$ it forks non-deterministically, one fork continuing to look for further copies of $\beta$ , 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^\prime$ , declaring $X$ to be a terminal, and adding all productions $X^\prime \rightarrow X$ to the grammar.

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

— David Lewis
źródło