Wie kann man beweisen, dass eine Grammatik eindeutig ist?

Mein Problem ist, wie kann ich beweisen, dass eine Grammatik eindeutig ist? Ich habe die folgende Grammatik:

und mache dies zu einer eindeutigen Grammatik, ich denke, es ist richtig:

• $S → S_1 ∣ S_2$

• $S_1 → \mbox{if } expression \mbox{ then } S ∣ \mbox{if } expression \mbox{ then } S_2 \mbox{ else } S_1$

• $S_2 → \mbox{if } expression \mbox{ then } S_2 \mbox{ else } S_2 ∣ statement$

Ich weiß, dass eine eindeutige Grammatik einen Analysebaum für jeden Begriff hat.

Es gibt (mindestens) einen Weg, die Eindeutigkeit einer Grammatik für die Sprache zu beweisen . Es besteht aus zwei Schritten:$G = (N,T,\delta,S)$$L$

1. Beweisen Sie .$L \subseteq \mathcal{L}(G)$
2. Man beweise.$[z^n]S_G(z) = |L_n|$

Der erste Schritt ist ziemlich klar: Zeigen Sie, dass die Grammatik (zumindest) die gewünschten Wörter generiert, das heißt, Richtigkeit.

Der zweite Schritt zeigt, dass so viele Syntaxbäume für Wörter der Länge wie Wörter der Länge - mit 1. Dies impliziert Eindeutigkeit. Es verwendet die Strukturfunktion von die auf Chomsky und Schützenberger [1] zurückgeht, nämlichn L n $G$$n$$L$$n$$G$

$\qquad \displaystyle S_G(z) = \sum_{n=0}^\infty t_nz^n$

mit die Anzahl der Syntaxbäume für Wörter der Länge . Natürlich müssen Siedamit dies funktioniert.G n | L n $t_n = [z^n]S_G(z)$$G$$n$$|L_n|$

Das Schöne ist, dass für kontextfreie Sprachen (normalerweise) leicht zu bekommen ist, obwohl es schwierig sein kann , eine geschlossene Form für finden. Transformiere in ein Gleichungssystem von Funktionen mit einer Variablen pro Nichtterminal:t n$S_G$$t_n$$G$

$\qquad \displaystyle \left[ A(z) = \sum\limits_{(A, a_0 \dots a_k) \in \delta} \ \prod\limits_{i=0}^{k} \ \tau(a_i)\ : A \in N \right] \text{ with } \tau(a) = \begin{cases} a(z) &, a \in N \\ z &, a \in T \\ \end{cases}.$

Dies mag einschüchternd aussehen, ist jedoch nur eine syntaktische Transformation, wie im Beispiel deutlich wird. Die Idee ist, dass generierte Terminalsymbole im Exponenten von gezählt werden. Da das System dieselbe Form wie , kommt in der Summe so oft vor, wie Terminals von generiert werden können . Überprüfen Sie Kuich [2] auf Details.G z n n $z$$G$$z^n$$n$$G$

Die Lösung dieses Gleichungssystems (Computeralgebra!) Ergibt ; Jetzt müssen Sie "nur" den Koeffizienten ziehen (in geschlossener, allgemeiner Form). Das TCS Cheat Sheet und die Computeralgebra können dies häufig.$S(z) = S_G(z)$

Beispiel

Betrachten Sie die einfache Grammatik mit Regeln$G$

$\qquad \displaystyle S \to aSa \mid bSb \mid \varepsilon$ .

Es ist klar, dass (Schritt 1, Beweis durch Induktion). Es gibt Palindrome der Länge wenn ist, sonst .2 $\mathcal{L}(G) = \{ww^R \mid w \in \{a,b\}^*\}$ nn$2^{\frac{n}{2}}$$n$$n$$0$

Aufstellung des Gleichungssystems ergibt

$\qquad \displaystyle S(z) = 2z^2S(z) + 1$

wessen Lösung ist

$\qquad \displaystyle S_G(z) = \frac{1}{1-2z^2}$ .

Die Koeffizienten von stimmen mit der Anzahl der Palindrome überein , so dass eindeutig ist.$S_G$ $G$

1. Die algebraische Theorie kontextfreier Sprachen von Chomsky, Schützenberger (1963)
2. Zur Entropie kontextfreier Sprachen von Kuich (1970)

Dies ist eine gute Frage, aber einige Googler hätten Ihnen gesagt, dass es keine allgemeine Methode für die Entscheidung über Mehrdeutigkeiten gibt. Sie müssen Ihre Frage daher präzisieren.

Für einige Grammatiken ist ein Induktionsnachweis (über Wortlänge) möglich.

Betrachten Sie zum Beispiel eine Grammatik über Σ = { a , b }, die durch die folgenden Regeln gegeben ist:$G$$\Sigma = \{a,b\}$

$\qquad \displaystyle S \to aSa \mid bSb \mid \varepsilon$

Alle Wörter der Länge in L ( G ) - es gibt nur ε - haben nur noch eine Ableitung.$\leq 1$$L(G)$$\varepsilon$

$\leq n$$n \in \mathbb{N}$

$w = w_1 w' w_n \in L(G) \cap \Sigma^n$$n > 0$$w_1 \in \Sigma$$w_1 = a$$S \to aSa$$w_1 = b$$S \to bSb$$w'$$w$

Dies wird schwieriger, wenn

• Es gibt mehrere Nicht-Terminals.
• Die Grammatik ist nicht linear und / oder
• Die Grammatik ist linksrekursiv.

Es kann hilfreich sein, den Anspruch auf alle sententialen Formen (wenn die Grammatik keine unproduktiven Nichtterminals hat) und "Wurzel" -Nichtterminals zu stärken.

Ich denke, die Umwandlung in die Greibacher Normalform bewahrt (Un-) Zweideutigkeit, diesen Schritt zuerst anzuwenden, kann die Linksrekursion gut erledigen.

Der Schlüssel besteht darin, ein Merkmal jedes Wortes zu identifizieren, das (mindestens) einen Ableitungsschritt festlegt. Der Rest folgt induktiv.

Grundsätzlich ist es ein Problem der Kindergeneration. Beginnen Sie mit dem ersten Ausdruck, und generieren Sie dessen untergeordnete Elemente. Führen Sie ihn weiterhin rekursiv aus (DFS), und prüfen Sie nach einigen Iterationen, ob Sie denselben erweiterten Ausdruck aus zwei verschiedenen untergeordneten Elementen generieren können. Wenn Sie das können, ist es nicht eindeutig. Es gibt jedoch keine Möglichkeit, die Laufzeit dieses Algorithmus zu bestimmen. Angenommen, es ist sicher, nachdem vielleicht 30 Levels von Kindern generiert wurden :) (Natürlich könnte es am 31. bombardieren)