Sprache ohne Zusammenhänge

In der formellen Sprachtheorie ist eine Sprache ohne Zusammenhänge eine durch eine Grammatik ohne Zusammenhänge erzeugte Sprache. Der Satz aller Sprachen ohne Zusammenhänge ist zum Satz von durch pushdown Automaten akzeptierten Sprachen identisch.

Beispiele

Eine archetypische Sprache ohne Zusammenhänge ist, die Sprache aller nichtleeren Schnuren der gleichen Länge, von denen die kompletten ersten Hälften 's sind, und, dessen komplette zweite Hälften 's. sind, wird durch die Grammatik erzeugt, und wird durch den pushdown Automaten akzeptiert, wo wie folgt definiert wird:

</Zentrum>

Sprachen ohne Zusammenhänge haben viele Anwendungen auf Programmiersprachen; zum Beispiel wird die Sprache aller richtig verglichenen Parenthesen durch die Grammatik erzeugt. Außerdem werden die meisten arithmetischen Ausdrücke durch Grammatiken ohne Zusammenhänge erzeugt.

Verschluss-Eigenschaften

Sprachen ohne Zusammenhänge werden unter den folgenden Operationen geschlossen. D. h. wenn L und P Sprachen ohne Zusammenhänge sind, sind die folgenden Sprachen ebenso ohne Zusammenhänge:

  • die Vereinigung von L und P
  • die Umkehrung von L
  • die Verkettung von L und P
  • der Stern von Kleene von L
  • das Image von L unter einem Homomorphismus
  • das Image von L unter einem umgekehrten Homomorphismus
  • die zyklische Verschiebung von L (die Sprache)

Sprachen ohne Zusammenhänge werden unter der Ergänzung, der Kreuzung oder dem Unterschied nicht geschlossen. Jedoch, wenn L eine Sprache ohne Zusammenhänge ist und D eine regelmäßige Sprache dann ist, sowohl ihre Kreuzung als auch ihr Unterschied sind Sprachen ohne Zusammenhänge.

Nichtverschluss unter der Kreuzung und Ergänzung

Die Sprachen ohne Zusammenhänge werden unter der Kreuzung nicht geschlossen. Das kann durch die Einnahme der Sprachen gesehen werden und, die beide ohne Zusammenhänge sind. Ihre Kreuzung ist, der, wie man zeigen kann, "nicht Zusammenhang frei" durch das pumpende Lemma für Sprachen ohne Zusammenhänge ist.

Sprachen ohne Zusammenhänge werden auch unter der Fertigstellung, bezüglich keiner Sprachen A und B geschlossen:.

Entscheidbarkeitseigenschaften

Die folgenden Probleme sind für willkürliche Grammatiken ohne Zusammenhänge A und B unentscheidbar:

  • Gleichwertigkeit: Ist?
  • ist? (Jedoch ist die Kreuzung einer Sprache ohne Zusammenhänge und einer regelmäßigen Sprache so ohne Zusammenhänge, wenn eine regelmäßige Sprache waren, wird dieses Problem entscheidbar.)
  • ist?
ist?

Die folgenden Probleme sind für willkürliche Sprachen ohne Zusammenhänge entscheidbar:

ist?ist

Eigenschaften von Sprachen ohne Zusammenhänge

  • Die Rückseite einer Sprache ohne Zusammenhänge ist ohne Zusammenhänge, aber die Ergänzung braucht nicht zu sein.
  • Jede regelmäßige Sprache ist ohne Zusammenhänge, weil sie durch eine Grammatik ohne Zusammenhänge beschrieben werden kann.
  • Die Kreuzung einer Sprache ohne Zusammenhänge und einer regelmäßigen Sprache ist immer ohne Zusammenhänge.
  • Dort bestehen Sie mit dem Zusammenhang empfindliche Sprachen, die nicht ohne Zusammenhänge sind.
  • Um zu beweisen, dass eine gegebene Sprache nicht ohne Zusammenhänge ist, kann man das pumpende Lemma für Sprachen ohne Zusammenhänge verwenden.

Syntaxanalyse

Die Bestimmung eines Beispiels des Mitgliedschaft-Problems; d. h. in Anbetracht einer Schnur, bestimmen Sie ob, wo die durch eine Grammatik erzeugte Sprache ist; ist auch bekannt als Syntaxanalyse.

Formell ist der Satz aller Sprachen ohne Zusammenhänge zum Satz von Sprachen identisch, die durch nichtdeterministische pushdown Automaten (NPDA) akzeptiert sind.

Praktische parser Algorithmen, d. h. Softwarerealisierungen von NPDA, schließen ein

Für die deterministische Unterklasse von Sprachen ohne Zusammenhänge gibt es mehrere wohl bekannte Syntaxanalyse-Methoden.

Siehe auch grammatisch analysierende Ausdruck-Grammatik als eine alternative Annäherung an die Grammatik und parser.

Siehe auch


Konkordat von Würmern / Koffein
Impressum & Datenschutz