Direkt zum Inhalt

Lexikon der Mathematik: Greibach-Sprache

spezielle kontextfreie Sprache GL (Grammatik) über einem siebenbuchstabigen Alphabet Σ1 mit der Eigenschaft, daß sich jede kontextfreie Sprache über einen Homomorphismus in GL einbetten läßt, d. h. zu jeder kontextfreien Sprache \(K\,\in \,{\Sigma }_{2}^{\ast }\) gibt es einen Homomorphismus \(h\,:\,{\Sigma }_{2}^{\ast }\,\to \,{\Sigma }_{1}^{\ast }\) mit \begin{eqnarray}L\backslash \{\varepsilon \}={h}^{-1}(GL).\end{eqnarray}

Damit kann die Greibach-Sprache als die „komplizierteste“ kontextfreie Sprache angesehen und für die Abschätzung des Mindestaufwandes für Algorithmen über kontextfreien Sprachen herangezogen werden, weil sich mit Hilfe des leicht auffindbaren Homomorphismus’ Probleme für beliebige kontextfreie Sprachen auf das entsprechende Problem für die Greibach-Sprache zurückführen lassen.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos