Nenne 3 Beispiele für wichtige formale Sprachen.
Beispiele für wichtige formale Sprachen sind
Die Sprache der Prädikatenlogik
Die regulären Sprachen
Die Programmiersprachen ( Java oder PHP)
Welches sind die zentralen Begriffe in der Analyse von Sprachen?
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.
Was ist ein Token?
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.
Wie werden formale Sprachen voneinander unterschieden?
Man unterscheidet formale Sprachen u. a. danach, mit welcher Form von Grammatik die Sprache erzeugt werden kann.
In der Theorie der formalen Sprachen gibt es Fragestellungen welche als Probleme bezeichnet werden.
Wie bezeichnet man diese Probleme?
Was ist das Ziel dieser dieser Fragestellungen?
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.
Benenne die 4 Fragestellungen (Entscheidungsprobleme)
welche in der Theorie der formalen Sprachen untersucht werden.
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.
Was ist die Chomsky-Hierarchie?
Aus welchen bestandteilen besteht eine Formale Grammatik?
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.
Was sind Nichtterminale?
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.
Woraus bestehen die Wörter einer Sprache?
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.
Was beschreiben die Regeln?
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:
Wie lautet die Definition „Regularität von Grammatiken“?
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.
Erzeugen Rechtsreguläre und linksreguläre Grammatiken die gleichen Sprachen?
Benne die 3 Charaktesierungen von regulären Sprachen.
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.
Welcher Sprachklasse der Chomsky-Hierarchie gehören die regulären Sprachen an?
In der Chomsky-Hierarchie werden sie als Typ-3-Grammatiken eingeordnet und die Sprachklasse als L3 bezeichnet.
Zähle die einzelnen Sprachen/Grammatiken der Chomsky-Hierarchie auf.
0: Rekursiv aufzählbar Sprache.
1: Kontextsensitive Sprache.
2: Kontextfreie Sprache.
3: Reguläre Sprache.
Daraus folgt.
Was bedeutet es wenn eine kontextfreie Sprache eindeutig oder mehrdeutig ist?
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.
Was beschreibt eine kontextfreie Grammatik?
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.
Was sind die Bestandteile einer kontextfreien Grammatik?
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.
Was ist die Backus-Naur-Form?
Und welche Programmiersprache wurde für die Beschreigung der Syntax verwendet?
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.
Was ist ein Uniform Resource Identifier?
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.
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).
Wozu wird das Pumping-Lemma für kontextfreie Sprachen verwendet?
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.
Gibt es ein Pumping-Lemma für kontextsensitive Sprachen?
Für kontextsensitive Sprachen gibt es kein Pumping-Lemma wie für reguläre und kontextfreie Sprachen.
Bitte betrachten Sie die folgende Grammatik:
Welchen Typ hat diese Grammatik?
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.
Bitte erläutern Sie die gemeinsame Grundidee der Pumping-Lemmas für reguläre und kontextfreie Sprachen.
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.
Hierarchie der Sprachklassen:
Zähle die Chomsky-Hierarchie auf.
Reguläre Sprachen ⊆
Kontextfreie Sprachen ⊆
Kontextsensitive Sprachen ⊆
Rekursiv aufzählbare Sprachen
Last changed4 days ago
