aboutsummaryrefslogtreecommitdiff
path: root/content
diff options
context:
space:
mode:
authorAdrian Kummerlaender2018-03-04 17:39:12 +0100
committerAdrian Kummerlaender2018-03-04 17:39:12 +0100
commitcd00998dd639c00ba2cadf53d02d2b45d6ebd15d (patch)
treec7305e7994fa731cb3397f6a939f2d853dbe03d4 /content
parent2891808b0ff414ce3279d0fc76911437dca7cead (diff)
downloadmath_reference_sheets-cd00998dd639c00ba2cadf53d02d2b45d6ebd15d.tar
math_reference_sheets-cd00998dd639c00ba2cadf53d02d2b45d6ebd15d.tar.gz
math_reference_sheets-cd00998dd639c00ba2cadf53d02d2b45d6ebd15d.tar.bz2
math_reference_sheets-cd00998dd639c00ba2cadf53d02d2b45d6ebd15d.tar.lz
math_reference_sheets-cd00998dd639c00ba2cadf53d02d2b45d6ebd15d.tar.xz
math_reference_sheets-cd00998dd639c00ba2cadf53d02d2b45d6ebd15d.tar.zst
math_reference_sheets-cd00998dd639c00ba2cadf53d02d2b45d6ebd15d.zip
Expand section on kontextfree grammars in TGI digest
Diffstat (limited to 'content')
-rw-r--r--content/tgi.tex28
1 files changed, 26 insertions, 2 deletions
diff --git a/content/tgi.tex b/content/tgi.tex
index 45b33d6..d5e6d84 100644
--- a/content/tgi.tex
+++ b/content/tgi.tex
@@ -381,7 +381,15 @@ $\mathcal{A}$ ist \emph{$\epsilon$-approximativ}, wenn:
Es gilt $\mathcal{L}_3 \subset \mathcal{L}_2 \subset \mathcal{L}_1 \subset \mathcal{L}_0$.
-\subsection*{Chomsky-Normalform}
+\subsection*{Kontextfreie Sprachen}
+
+Die Klasse kontextfreier Sprachen ist abgeschlossen ggü. Vereinigung, Konkatenation und Kleenschem Abschluss. Sie ist nicht abgeschlossen ggü. Komplementbildung und Durchschnitt.
+
+\spacing
+
+Für eine kontextfreie $G$ kann in polynomialer Zeit entschieden werden, ob $L(G)$ endlich ist.
+
+\subsubsection*{Chomsky-Normalform}
Eine kontextfreie Grammatik ist in \emph{Chomsky-Normalform}, wenn alle Regeln von Form $A \to BC$ oder $A \to a$ mit $A,B,C \in V$ und $a \in \Sigma$ sind.
@@ -393,10 +401,26 @@ Jede nicht $\epsilon$ erzeugende kontextfreie Grammatik ist in Chomsky-Normalfor
Entscheidet für kontextfreie Grammatik $G$ in Chomsky-Normalform und Wort $w \in \Sigma^*$ das Wortproblem in Zeit $\mathcal{O}(|R|\cdot |w|^3)$ wobei $|R|$ Anzahl der Regeln in $G$ ist.
-\subsection*{Greibach-Normalform}
+\subsubsection*{Greibach-Normalform}
Eine kontextfreie Grammatik ist in \emph{Greibach-Normalform}, wenn alle Regeln von Form $A \to a\alpha$ für $A \in V, a \in \Sigma$ und $\alpha \in V^*$ sind.
\spacing
Jede nicht $\epsilon$ erzeugende kontextfreie Grammatik ist in Greibach-Normalform überführbar.
+
+\subsubsection*{Unentscheidbare Probleme}
+
+Seien $G, G_1, G_2$ kontextfreie Grammatiken.
+
+Die folgenden Probleme sind nicht entscheidbar:
+
+\begin{enumerate}
+\item Gilt $L(G_1) \cap L(G_2) = \emptyset$
+\item $\forall w \in L(G) : $ Syntaxbaum von $w$ ist eindeutig
+\item Ist $(L(G))^c$ kontextfrei
+\item Ist $L(G_1) \cap L(G_2)$ kontextfrei
+\item Gilt $L(G) = \Sigma^*$
+\item Gilt $L(G_1) = L(G_2)$
+\item Gilt $L_(G_1) \subseteq L(G_2)$
+\end{enumerate}