4. Formale Sprachen und Grammatiken

Beispiele für wichtige formale Sprachen sind

• Die Sprache der Prädikatenlogik

• Die regulären Sprachen

• Die Programmiersprachen ( Java oder PHP)

• Syntax: Die Syntax einer Sprache beschreibt, welche Worte oder Sätze in der Sprache erlaubt sind

• Die Semantik: Die Semantik einer Sprache beschreibt, was die Worte oder Sätze der Sprache bedeuten

• Die Pragmatik: Hier geht es darum zu beschreiben, wie eine Sprache genutzt werden sollte, z. B. welche Sprache für welchen Zweck geeignet ist oder welche Sprachkonstrukte wann verwendet werden sollten.

In einer Formalen Sprache werden sogenannte Zeichen genutzt.

• Diese können ein ganzes Schlüsselwort oder ein kompletter Variablenname einer Programmiersprache sein.

• Derartige Zeichen werden oft als Token bezeichnet.

• Man unterscheidet formale Sprachen u. a. danach, mit welcher Form von Grammatik die Sprache erzeugt werden kann.

• Diese Probleme werden als Entscheidungsprobleme bezeichnet, weil sie die Frage nach einer (Ja-/Nein-)Entscheidung stellen.

• Ziel ist es jeweils, ein allgemeines Verfahren, also einen Algorithmus, zu finden, der für alle Werte, in diesem Fall also alle Sprachen und Worte, die entsprechende Frage entscheidet.

• Wortproblem: Gegeben seien eine formale Sprache und ein bestimmtes Wort, ist dieses Wort in der Sprache enthalten? Passt beispielsweise ein bestimmtes Wort zu einem vorgegebenen regulären Ausdruck?

• Äquivalenzproblem: Gegeben seien zwei verschiedene Beschreibungen von formalen Sprachen L1 und L2, sind die Beschreibungen äquivalent, d. h. die beschriebenen Sprachen gleich?

• Leerheitsproblem: Gegeben sei eine Beschreibung einer formalen Sprache, gibt es in dieser Sprache mindestens ein Wort oder ist die Sprache gleich der leeren Menge? Dieses Problem ist verwandt mit der Frage nach der Erfüllbarkeit einer logischen Formel.

• Endlichkeitsproblem: Ist die Sprache endlich, umfasst also nur endlich viele Worte?

• Ja

  • denn dann kann man die Worte der Sprache einfach auflisten und gegen das gesuchte Wort vergleichen. Da die Auflistung für eine endliche Sprache endet, erhält man auf jeden Fall eine Antwort.

Die Chomsky Hierarchie stellt eine Hierarchie von Klassen formaler Grammatiken dar, welche formale Sprachen erzeugen.

• Einer endlichen Menge von Variablen welche als Nichtterminale bezeichnet werden

• einer Startvariable

• einem Alphabet welche als Terminale bezeichnet werden.

• einer endlichen Menge von Regeln, auch Produktionsregeln genannt.

• Die Nichtterminale sind Zeichen, die in den Produktionsregeln zur Erzeugung von Worten verwendet werden, die aber am Ende alle durch Terminale ersetzt werden müssen.

• In einer einfachen Grammatik eines Ausschnittes der deutschen Sprache könnte man beispielsweise die Nichtterminale

  • „<Satz>“, „<Subjekt>“, „<Prädikat>“, „<Objekt>“, „<Artikel>“ und „<Substantiv>“ verwenden.

Die Worte der Sprache bestehen nur aus Terminalen.

• Als kleinen Ausschnitt aus der deutschen Sprache können wir beispielsweise das „Alphabet“ bestehend aus den Zeichen {„der“, „die“, „das“, „Katze“, „frisst“, „Maus“} definieren.

Die Regeln beschreiben, wie Zeichenketten bestehend aus Nichtterminalen und Terminalen in neue, ebenfalls aus Nichtterminalen und Terminalen bestehende Zeichenketten überführt werden können. In unserem Ausschnitt der deutschen Sprache sind das beispielsweise die Regeln:

Seien T und U NIchterminalsymbole, sei a ein Terminalsymbol und es bezeichne kleinepsilon das Leere Wort. Eine Grammatik heißt rechtsregulär, wenn jede ihrer Produktionsregeln eine der folgenden drei Formen hat:

Eine Grammatik heißt linksregulär, wenn jede ihrer Produktionsregeln eine der folgenden drei Formen hat:

Eine Grammatik heißt regulär, wenn sie rechtsregulär oder linksregulär ist.

Ja

• Die Sprache wird durch einen endlichen Automaten akzeptiert.

• Die Sprache wird durch einen regulären Ausdruck definiert.

• Die Sprache wird durch eine reguläre Grammatik erzeugt.

• In der Chomsky-Hierarchie werden sie als Typ-3-Grammatiken eingeordnet und die Sprachklasse als L3 bezeichnet.

0: Rekursiv aufzählbar Sprache.

1: Kontextsensitive Sprache.

2: Kontextfreie Sprache.

3: Reguläre Sprache.

Daraus folgt.

• Eine (kontextfreie) Grammatik, in der es für jedes Wort der Sprache genau einen Ableitungsbaum gibt, heißt eindeutig.

• Gibt es Worte mit mehreren unterschiedlichen Ableitungsbäumen, dann heißt die Grammatik mehrdeutig.

• Eine kontextfreie Grammatik beschreibt, wie man Zeichenketten aus einer Sprache mit bestimmten Regeln erzeugen kann.

• Sie ist "kontextfrei", weil die Regeln unabhängig davon sind, wo sie angewendet werden.

• Nichtterminale: Symbole, die für Kategorien oder "Platzhalter" stehen (z. B. ein Satz, eine Zahl oder ein Wort). Sie werden oft mit Großbuchstaben geschrieben, z. B. SSS, AAA.

• Terminalsymbole: Die "Bausteine", aus denen die Sprache besteht. Das sind konkrete Zeichen oder Wörter, z. B. aaa, bbb, +++, 000.

• Regeln (Produktionen): Diese sagen, wie ein Nichtterminal durch andere Nichtterminale und/oder Terminalsymbole ersetzt werden kann. Z. B.: S→aSbS \to aSbS→aSb.

• Startsymbol: Das Nichtterminal, mit dem die Beschreibung der Sprache beginnt, oft SSS.

  
  

• Die Backus-Naur-Form ist eine Beschreibungsform für kontextfreie Sprachen, die nach John W. Backus und Peter Naur benannt ist, zwei Informatikern,

• die diese Form für die Beschreibung der Syntax der Programmiersprache Algol 60 verwendeten.

Uniform Resource Identifier

• In Webtechnologien verwendete eindeutige Zeichenfolge, die eine logische oder physische Ressource, beispielsweise eine Webseite, identifiziert.

  
  

• Eine URI ist der umfassendere Begriff. Sie identifiziert eine Ressource entweder durch ihren Namen (URN), ihren Standort (URL) oder beides.

• Eine URL ist eine spezielle Art von URI, die sich auf den Standort und den Zugriffsweg konzentriert.

Analogie:

Stell dir vor, du suchst ein Buch:

• Eine URI sagt: „Das Buch heißt ISBN 978-3-16-148410-0

  

  .“ (Identifikation durch den Namen oder eine Beschreibung).

• Eine URL sagt: „Das Buch liegt im Regal A, Fach 3 in der Stadtbibliothek.“ (Identifikation durch Standort und Zugriff).

• Auch das Pumping-Lemma für kontextfreie Sprachen wird in erster Linie dazu verwendet nachzuweisen, dass eine bestimmte Sprache nicht kontextfrei ist, da das Pumping-Lemma für die Sprache nicht gilt.

• Für kontextsensitive Sprachen gibt es kein Pumping-Lemma wie für reguläre und kontextfreie Sprachen.

• Die Grammatik erfüllt die Anforderungen an eine kontextfreie Grammatik, da sie auf der linken Seite der Grammatik nur Nichtterminalsymbole enthält.

• Durch die Regeln 2 und 3 ist sie aber weder rechts- noch linksregulär und damit keine reguläre Grammatik.

• Es handelt sich also um eine kontextfreie (Typ-2-)Grammatik.

• Mithilfe der Pumping-Lemmas kann man zeigen, dass Worte der jeweiligen Sprachen ab einer gewissen Größe eine Schleife enthalten müssen, die dann auch beliebig oft durchlaufen werden kann.

• Damit kann man auch weitere Worte der Sprache konstruieren, was vor allem hilfreich ist, um zu zeigen, dass eine bestimmte Sprache nicht regulär bzw. kontextfrei ist, da sie nicht alle auf diesem Weg konstruierten Worte enthält.

1. Reguläre Sprachen ⊆

2. Kontextfreie Sprachen ⊆

3. Kontextsensitive Sprachen ⊆

4. Rekursiv aufzählbare Sprachen