(Vorwissen zu Formalen Sprachen)

Formale Sprachen ähneln menschlichen Sprachen

💡 Was ist eine formale Sprache? (mit Beispielen)

Eine formale Sprache ist eine Menge von Zeichenketten, die nach bestimmten Regeln gebildet werden. Diese Regeln, auch Grammatik genannt, legen fest, welche Kombinationen von Zeichen zulässig sind. Formale Sprachen sind im Gegensatz zu natürlichen Sprachen vollständig eindeutig und präzise.

Bestandteile einer formalen Sprache:

Alphabet: Das Alphabet ist eine endliche Menge von Symbolen, aus denen die Sprache gebildet wird.

Beispiel: In der binären Sprache ist das Alphabet {0, 1}, also bestehen alle Zeichenfolgen aus den Symbolen “0” und “1”.

Zeichenkette: Eine Sequenz von Symbolen aus dem Alphabet.

Beispiel: Eine gültige Zeichenkette im binären Alphabet wäre “101” oder “0110”.

Grammatik: Die Regeln, die festlegen, wie Zeichen und Zeichenketten aus dem Alphabet kombiniert werden dürfen, um gültige Ausdrücke zu bilden.

Beispiel: In der Grammatik einer einfachen arithmetischen Sprache könnte eine Regel lauten: “Eine Zahl gefolgt von einem Operator (+, -, *, /) und dann eine weitere Zahl” → “3 + 4” ist eine gültige Zeichenkette.

Beispiele für formale Sprachen:

Reguläre Sprache: Besteht aus Zeichenketten, die durch reguläre Ausdrücke beschrieben werden können.

Beispiel: Der reguläre Ausdruck a*b beschreibt eine Sprache, die alle Zeichenketten enthält, die aus einer beliebigen Anzahl von “a” gefolgt von einem “b” bestehen. Beispiele: “b”, “ab”, “aaab”.

Programmiersprachen: Eine Menge von Anweisungen und Ausdrücken, die nach strikten Regeln formuliert sind.

Beispiel: In der Programmiersprache Python könnte eine gültige Zeichenkette sein: print("Hello, World!"). Die Syntax dieser Zeichenkette folgt einer formalen Grammatik.

Formale Sprachen sind essenziell, um Computern mitzuteilen, was sie tun sollen. Ohne eine klare Struktur, wie sie durch formale Sprachen gegeben ist, könnten Programme nicht korrekt analysiert oder ausgeführt werden.

Allgemeines Wissen zur Chomsky-Hierarchie

1. Erklärung der Chomsky-Hierarchie

Die Chomsky-Hierarchie ist ein Konzept aus der theoretischen Informatik und Linguistik, das verschiedene Klassen von formalen Sprachen beschreibt. Jede dieser Klassen ist durch die Art von Grammatik definiert, die für die Sprache verwendet wird, sowie durch die Komplexität der Erkennung durch einen Automaten. Die Hierarchie besteht aus vier Stufen:

Typ-0-Sprachen (rekursiv aufzählbare Sprachen):

Diese sind die allgemeinsten formalen Sprachen und können von einer Turing-Maschine erkannt werden.

Grammatik: Keine Einschränkungen, jede Regel ist erlaubt.

Verwendung: Sie umfassen alle berechenbaren Sprachen.

Typ-1-Sprachen (kontextsensitive Sprachen):

Jede Produktion in der Grammatik hat die Form: α → β, wobei die Länge von α nicht größer ist als die Länge von β (|α| ≤ |β|).

Erkennung: Linear beschränkte Automaten (eine eingeschränkte Form der Turing-Maschine).

Verwendung: Komplexe formale Sprachen, die in der Praxis weniger relevant sind.

Typ-2-Sprachen (kontextfreie Sprachen):

Eine der bekanntesten Klassen in der Informatik. Hier ist jede Produktion in der Grammatik der Form: A → α, wobei A ein Nichtterminal ist und α eine beliebige Folge von Terminal- und Nichtterminalsymbolen.

Erkennung: Kellerautomaten (ein Stack wird verwendet).

Verwendung: Diese Sprachen werden häufig zur Definition von Programmiersprachen und Compilern verwendet.

Typ-3-Sprachen (reguläre Sprachen):

Die einfachste Klasse von Sprachen. Die Produktionsregeln sind auf die Form A → a oder A → aB beschränkt, wobei A und B Nichtterminalsymbole und a ein Terminalsymbol ist.

Erkennung: Endliche Automaten.

Verwendung: Reguläre Sprachen werden häufig für Suchmuster, einfache Syntax und lexikalische Analysen verwendet.

Spickzettel zur Chomsky-Hierarchie

1. Erklärung der Chomsky-Hierarchie

Die Chomsky-Hierarchie beschreibt vier Klassen von formalen Sprachen, basierend auf der Komplexität ihrer Grammatik und der Art des Automaten, der sie erkennt:

Typ-0-Sprachen: Allgemeinste Sprachen, erkennbar durch Turing-Maschinen, ohne Einschränkungen in der Grammatik.

Typ-1-Sprachen: Kontext-sensitive Sprachen, die von linear beschränkten Automaten erkannt werden; Regeln sind in der Form |α| ≤ |β|.

Typ-2-Sprachen: Kontextfreie Sprachen, erkennbar durch Kellerautomaten; wichtig für Programmiersprachen.

Typ-3-Sprachen: Reguläre Sprachen, die von endlichen Automaten erkannt werden; verwendet für Suchmuster und lexikalische Analysen.

BNF

1. Erkunden Sie die Historie des Kürzels BNF.

Backus-Naur-Form (BNF): Formale Notation zur Beschreibung der Syntax formaler Sprachen, speziell Programmiersprachen.
Entwickelt von John Backus (1960er Jahre) zur Beschreibung der Programmiersprache ALGOL 60.
Peter Naur verfeinerte und standardisierte BNF, was zu ihrer Verbreitung führte.
Wichtig für die präzise Spezifikation der Syntax von Programmiersprachen.
Wesentlich für die Definition der Regeln, nach denen Programme geschrieben werden.
BNF ist ein Standard für die formale Spezifikation und Grundlage moderner Erweiterungen wie der erweiterten BNF (EBNF).
Relevanz: Wichtiger Bestandteil bei der Entwicklung von Compilern.

What the Backus???

Die Backus-Naur-Form (BNF) ist ein Werkzeug, das in der Informatik verwendet wird, um die Regeln und Strukturen von Programmiersprachen klar und präzise festzulegen. Man kann es sich wie eine Art “Grammatik” für Programmiersprachen vorstellen, ähnlich wie eine Sprache festlegt, wie Sätze aufgebaut sein müssen.

John Backus hat BNF in den 1960er Jahren entwickelt, um die Programmiersprache ALGOL 60 zu beschreiben.

Peter Naur hat diese Methode weiter verfeinert und standardisiert, was zu ihrer breiten Anwendung geführt hat.

Die BNF ist wichtig, weil sie es Entwicklern ermöglicht, die Regeln für das Schreiben von Programmen eindeutig festzulegen, damit Computer sie richtig verstehen und verarbeiten können.

Sie ist eine Standardmethode geworden, um Programmiersprachen zu definieren und spielt eine zentrale Rolle bei der Entwicklung von Compilern (Programme, die den Code eines Entwicklers in eine für den Computer ausführbare Form übersetzen).

Im Grunde hilft BNF also dabei, die Regeln zu schaffen, nach denen Programme aufgebaut werden müssen, und ist ein grundlegendes Werkzeug für die Entwicklung von Software.

1. Beispiel: Definition einer Ziffer in BNF (einfach)

<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

<digit>: Dies ist das Nicht-Terminalsymbol (oder Platzhalter), das durch die Ziffern 0 bis 9 ersetzt werden kann.
0, 1, 2, … 9: Diese sind Terminalsymbole (konkrete Werte), die die möglichen Ziffern darstellen.
Der „::=“ Operator zeigt an, dass das Nicht-Terminalsymbol „<digit>“ durch eine der Terminalsymbole ersetzt werden kann. (wird manchmal auch als → geschrieben)

2. Beispiel: Definition der Uhrzeit im 24-Stunden-Format in BNF (mittelschwer)

<hour>    ::= 0 | 1 | 2 | … | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23
<minute>  ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | … | 59
<time>    ::= <hour> ":" <minute>

Erklärung:

<hour>: Definiert die Stunde im 24-Stunden-Format. Gültige Werte sind 0 bis 23.
<minute>: Definiert die Minuten, die von 0 bis 59 reichen.
<time>: Eine Uhrzeit besteht aus einer Stunde <hour>, gefolgt von einem Doppelpunkt ":", und dann den Minuten <minute>.

Beispiele für gültige Uhrzeiten:

08:30 (8 Uhr 30 Minuten)
23:59 (23 Uhr 59 Minuten)
00:00 (Mitternacht)

3.Beispiel: Definition einer E-Mail-Adresse in BNF (schwer)

<letter>        ::= "a" | "b" | "c" | "d" | … | "z" | "A" | "B" | "C" | … | "Z"
<digit>         ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<special_char>  ::= "." | "-" | "_"
 
<local_part>    ::= <letter> | <digit> | <special_char> | <local_part> <letter> | <local_part> <digit> | <local_part> <special_char>
 
<domain>        ::= <letter> | <letter> <domain> | <domain> "." <letter> <letter> <letter>
 
<email>         ::= <local_part> "@" <domain>

Erklärung:

<letter>: Ein einzelner Buchstabe (groß oder klein).
<digit>: Eine einzelne Ziffer.
<special_char>: Spezielle Zeichen, die in der lokalen Adresse einer E-Mail erlaubt sind (z. B. Punkt, Bindestrich, Unterstrich).
<local_part>: Der Teil vor dem „@“ in einer E-Mail-Adresse. Dies kann eine Kombination aus Buchstaben, Ziffern und bestimmten Sonderzeichen sein.
<domain>: Der Teil nach dem „@“, der die Domain der E-Mail-Adresse darstellt. Dieser Teil besteht aus Buchstaben und Punkten, wobei mindestens zwei bis drei Buchstaben für die Top-Level-Domain (z. B. „com“, „org“) am Ende erforderlich sind.
<email>: Eine vollständige E-Mail-Adresse, die aus einem lokalen Teil, dem Zeichen „@“, und einer Domain besteht.

Was bedeutet `<local_part> <letter> | <local_part> <digit> | <local_part> <special_char>`?

Grundidee:

Die Definition von <local_part> in der BNF ist rekursiv. Das bedeutet, dass der <local_part> sich selbst enthält, um längere Zeichenketten aufzubauen.

Rekursion: Eine Regel, die auf sich selbst verweist, um komplexere Strukturen zu erzeugen.

Schauen wir uns das genauer an:

<local_part> ::= <letter> | <digit> | <special_char> | <local_part> <letter> | <local_part> <digit> | <local_part> <special_char>

Bedeutung der einzelnen Teile:

<letter> | <digit> | <special_char>:
- Das bedeutet, der <local_part> kann mit einem einzelnen Zeichen beginnen, entweder einem Buchstaben, einer Ziffer oder einem Sonderzeichen.
- Beispiele: a, 1, _
<local_part> <letter>:
- Das bedeutet, der <local_part> kann aus einem vorherigen <local_part> (z. B. einem Buchstaben, einer Ziffer oder einem Sonderzeichen) bestehen, gefolgt von einem weiteren Buchstaben.
- Beispiel: Wenn <local_part> “a” ist, dann könnte <local_part> <letter> “ab” ergeben.
<local_part> <digit>:
- Ähnlich wie oben, aber diesmal wird eine Ziffer hinzugefügt.
- Beispiel: Wenn <local_part> “a” ist, dann könnte <local_part> <digit> “a1” ergeben.
<local_part> <special_char>:
- In diesem Fall wird ein Sonderzeichen hinzugefügt.
- Beispiel: Wenn <local_part> “john” ist, dann könnte <local_part> <special_char> “john.” (mit einem Punkt) ergeben.

Einfacher zusammengefasst:

Das bedeutet, dass der <local_part> sich selbst erweitern kann, indem er neue Buchstaben, Ziffern oder Sonderzeichen hinzufügt.
Dadurch entsteht eine Zeichenkette, die immer länger wird.

Schrittweiser Aufbau eines Beispiels:

Erster Schritt: <local_part> ::= <letter>
Beispiel: j (eine einzelne Ziffer oder Buchstabe).
Zweiter Schritt: <local_part> ::= <local_part> <letter>
Beispiel: jo (jetzt haben wir “j” gefolgt von einem weiteren Buchstaben “o”).
Dritter Schritt: <local_part> ::= <local_part> <special_char>
Beispiel: john. (jetzt haben wir “john” gefolgt von einem Punkt).
Vierter Schritt: <local_part> ::= <local_part> <letter>
Beispiel: john.d (wir fügen ein weiteres Zeichen hinzu).

So können wir schrittweise komplexere Zeichenketten wie john.doe oder alice_123 aufbauen.

Zusammenfassung:

Durch die rekursive Regel kannst du immer wieder Buchstaben, Ziffern oder Sonderzeichen an den <local_part> anhängen, um eine vollständige Zeichenkette zu bilden.
Jede dieser Rekursionen fügt ein weiteres Zeichen hinzu, bis die vollständige E-Mail-Adresse gebildet ist.

Beispiele für gültige E-Mail-Adressen:

john.doe@example.com
alice_123@my-domain.org
user.name123@domain.co.uk

2. Beschreiben Sie die folgenden Mengen mittels BNF:

a) Matrikelnummern

<Matrikelnummer> ::= <Ziffer außer Null> <Ziffer> <Ziffer> <Ziffer> <Ziffer> <Ziffer> <Ziffer>
<Ziffer> ::= 0 | <Ziffer außer Null>
<Ziffer außer Null> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Beispiel:

Um die Korrektheit der BNF anhand des Beispiels 1234567 zu zeigen, gehen wir Schritt für Schritt durch:

Matrikelnummer: 1234567
Die BNF-Regel lautet:

<Matrikelnummer> ::= <Ziffer außer Null> <Ziffer> <Ziffer> <Ziffer> <Ziffer> <Ziffer> <Ziffer>

Überprüfung der ersten Ziffer:
- Erste Ziffer: 1
- Diese Ziffer entspricht der Regel:

<Ziffer außer Null> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Überprüfung der restlichen Ziffern:
- Ziffern: 2, 3, 4, 5, 6, 7
- Diese Ziffern erfüllen die Regel:

<Ziffer> ::= 0 | <Ziffer außer Null>

Alle diese Ziffern sind entweder 0 oder Ziffern außer Null.

Damit entspricht die Matrikelnummer 1234567 der definierten BNF. Die erste Ziffer ist keine 0, und die restlichen Ziffern sind gültige Ziffern gemäß der BNF.

Weiter mögliche Lösung (rekursiv)

<Matrikelnummer> ::= <Ziffer außer Null> <Rest>
<Rest> ::= <Ziffer> <Rest> | <Ziffer>
<Ziffer> ::= 0 | <Ziffer außer Null>
<Ziffer außer Null> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Erklärung:

<Matrikelnummer>: Die Matrikelnummer beginnt mit einer Ziffer außer Null, gefolgt von einem Rest.
<Rest>: Der Rest ist rekursiv definiert. Entweder besteht er aus einer weiteren Ziffer und einem weiteren Rest oder endet mit einer Ziffer. Diese Rekursion endet, sobald die Matrikelnummer vollständig ist (also 7 Ziffern enthält).
<Ziffer>: Kann 0 oder eine Ziffer außer Null sein.
<Ziffer außer Null>: Ist eine Ziffer von 1 bis 9.

Beispiel für 1234567:

1234567 entspricht der Regel:
- 1 ist <Ziffer außer Null>.
- 234567 ist der Rest.
Der Rest wird weiter aufgeteilt:
- 2 ist <Ziffer>, und der nächste Rest ist 34567.
- 3 ist <Ziffer>, und der nächste Rest ist 4567, und so weiter, bis der Rest nur noch eine Ziffer ist.

b) Bielefelder Kfz-Kennzeichen

<Bielefelder Kfz-Kennzeichen> ::= "BI" <Buchstabe> [<Buchstabe>] <Ziffer> [<Ziffer>] [<Ziffer>] [<Ziffer>]
<Buchstabe> ::= [A-Z]
<Ziffer> ::= [0-9]

Erklärung:

<Bielefelder Kfz-Kennzeichen>: Beginnt immer mit “BI” für Bielefeld, gefolgt von einem Buchstaben (Pflicht), einem optionalen zweiten Buchstaben, einer Ziffer und optional bis zu drei weiteren Ziffern.
<Buchstabe>: Ist ein beliebiger Buchstabe von A bis Z.
<Ziffer>: Ist eine Ziffer von 0 bis 9.

Die eckigen Klammern [] bedeuten, dass der eingeschlossene Teil optional ist. In diesem Fall:

Es kann ein zweiter Buchstabe folgen, ist aber nicht erforderlich.
Nach der ersten Ziffer können bis zu drei weitere Ziffern folgen, aber auch das ist optional.

Beispiele:

BI A 123
BI AB 4
BI C 56
BI Z 7890

Diese Kennzeichen sind gültig nach der oben beschriebenen BNF. fUe

3. Charakterisieren Sie Produktion (a+b) * (c-d) mit Hilfe von BNF.

Meine Lösung:

<Ausdruck> ::= <Term> "*" <Term>
<Term> ::= "(" <Operand> <Operator> <Operand> ")"
<Operand> ::= "a" | "b" | "c" | "d"
<Operator> ::= "+" | "-"

Erklärung:

<Ausdruck>: Beschreibt den gesamten Ausdruck, der aus zwei Termen besteht, die durch den Multiplikationsoperator * verbunden sind.
<Term>: Ein Term ist ein Unterausdruck in Klammern, der zwei Operanden enthält, die durch einen Operator (+ oder -) verbunden sind. In diesem Fall haben wir zwei Terme:
- Der erste Term ist (a + b)
- Der zweite Term ist (c - d)
<Operand>: Operanden sind die Variablen a, b, c und d.
<Operator>: Der Operator kann entweder + oder - sein.

Beispiel:

Der Ausdruck (a + b) * (c - d) würde folgendermaßen analysiert werden:

1. <Ausdruck> ::= <Term> "*" <Term>
   - Der Ausdruck besteht aus zwei Termen, die durch `*` verbunden sind.
 
2. Der erste Term:
   - <Term> ::= "(" <Operand> <Operator> <Operand> ")"
   - Operand: a
   - Operator: +
   - Operand: b
   - Ergebnis: `(a + b)`
 
3. Der zweite Term:
   - <Term> ::= "(" <Operand> <Operator> <Operand> ")"
   - Operand: c
   - Operator: -
   - Operand: d
   - Ergebnis: `(c - d)`

Insgesamt ergibt dies den Ausdruck: (a + b) * (c - d).

Musterlösung von deinem Prof.

Die Musterlösung von deinem Professor ist fehlerhaft

Hinweis: Die Musterlösung ist fehlerhaft, da Klammern fehlen. Ohne Klammern wird der Ausdruck nach den Prioritätsregeln für Operatoren berechnet, was zu einer falschen Auswertung führt. Der Ausdruck a + b * c - d würde als a + (b * c) - d interpretiert. Um sicherzustellen, dass (a + b) und (c - d) zuerst berechnet werden, sollten die Klammern ergänzt werden.

Ich habe es unten ausgebessert

Erklärung der Musterlösung

Die gegebene BNF beschreibt einen Ausdruck, der aus einer Summe und einer Differenz besteht, die durch den Multiplikationsoperator * verbunden sind:

<p1> ::= <Summe> * <Differenz>
<Summe> ::= <Summand> | <Summand> + <Summand>
<Differenz> ::= <Minuend> | <Minuend> - <Minuend>
<Summand> ::= a | b
<Minuend> ::= c | d

Beispiel:

Für den Ausdruck a + b * c - d:

<Summe> ergibt a + b.
<Differenz> ergibt c - d.

Problem: Ohne Klammern wird der Ausdruck nach den Operator-Prioritätsregeln als a + (b * c) - d ausgewertet, was zu einer falschen Berechnung führt. Die Klammern sind entscheidend, um sicherzustellen, dass (a + b) und (c - d) zuerst berechnet werden.

Verbesserung:

Die Klammern sollten ergänzt werden:

<p1> ::= "(" <Summe> ")" * "(" <Differenz> ")"

Dies stellt die korrekte Reihenfolge der Berechnungen sicher.

Nachhilfe Informatik

Explorer

2-Formale Sprachen

(Vorwissen zu Formalen Sprachen)

💡 Was ist eine formale Sprache? (mit Beispielen)

Bestandteile einer formalen Sprache:

Beispiele für formale Sprachen:

1. Erklärung der Chomsky-Hierarchie

1. Erklärung der Chomsky-Hierarchie

BNF

1. Erkunden Sie die Historie des Kürzels BNF.

1. Beispiel: Definition einer Ziffer in BNF (einfach)

2. Beispiel: Definition der Uhrzeit im 24-Stunden-Format in BNF (mittelschwer)

Erklärung:

Beispiele für gültige Uhrzeiten:

3.Beispiel: Definition einer E-Mail-Adresse in BNF (schwer)

Erklärung:

Was bedeutet <local_part> <letter> | <local_part> <digit> | <local_part> <special_char>?

Grundidee:

Bedeutung der einzelnen Teile:

Einfacher zusammengefasst:

Schrittweiser Aufbau eines Beispiels:

Zusammenfassung:

Beispiele für gültige E-Mail-Adressen:

2. Beschreiben Sie die folgenden Mengen mittels BNF:

a) Matrikelnummern

Beispiel:

Weiter mögliche Lösung (rekursiv)

Erklärung:

Beispiel für 1234567:

b) Bielefelder Kfz-Kennzeichen

Erklärung:

Beispiele:

3. Charakterisieren Sie Produktion (a+b) * (c-d) mit Hilfe von BNF.

Meine Lösung:

Erklärung:

Beispiel:

Musterlösung von deinem Prof.

Erklärung der Musterlösung

Beispiel:

Verbesserung:

Weitere empfehlenswerte Ressourcen

Graphansicht

Inhaltsverzeichnis

Backlinks

Was bedeutet `<local_part> <letter> | <local_part> <digit> | <local_part> <special_char>`?