michael.eichberg@dhbw.de, Raum 149B
1.1
Die Folien sind teilweise inspiriert von oder basierend auf Lehrmaterial von Prof. Dr. Ritterbusch und Theoretische Informatik - kurzgefasst von Prof. Dr. Uwe Schöning.
Formale Sprachen sind ein zentraler Aspekt der theoretischen Informatik.
Nutzungsinterface zwischen Computer und Mensch
Grundlage für Programmiersprachen
Es gibt unterschiedliche Klassen und Modelle formaler Sprachen:
Erkennbarkeit und Ausdruckskraft
Anforderungen an Computermodelle zur Erkennbarkeit
Komplexität von Verfahren zur Erkennung
Die Kleene-Abschlüsse und Multiplikationen werden später in regulären Ausdrücken auf Wörtern verwendet, damit ist dann der Abschluss oder das kartesische Produkt der Menge mit genau diesem Wort gemeint.
Alphabet Σ = {a,el,en,g,l,ste}
Gegeben sei das Alphabet \(\Sigma = \{a,el,en,g,l,ste\}\). Welche der folgenden Worte liegen in \(\Sigma ^4\)?
\(\omega _1\) = galgen, \(\omega _2\) = stelle, \(\omega _3\) = sagen, \(\omega _4\) = lagen, \(\omega _5\) = allen, \(\omega _6\) = aalen
Alphabet Σ = {e,en,in,r,t,u}
Gegeben sei das Alphabet \(\Sigma = \{e,en,in,r,t,u\}\). Welche der folgenden Worte liegen in \(\Sigma ^5\)?
\(\omega _1\) = reiner, \(\omega _2\) = teurer, \(\omega _3\) = treuer, \(\omega _4\) = teuren, \(\omega _5\) = retten, \(\omega _6\) = teuer
Alphabet Σ = {e,g,in,l,s,ter}
Gegeben sei das Alphabet \(\Sigma = \{e,g,in,l,s,ter\}\). Welche der folgenden Worte liegen in \(\Sigma ^*\)?
\(\omega _1\) = tester, \(\omega _2\) = seile, \(\omega _3\) = lines, \(\omega _4\) = segel, \(\omega _5\) = seinen, \(\omega _6\) = erster
Wörter bestimmen
Bestimmen Sie die Wörter der folgenden Sprache:
\(L= \{acx^m (zq)^n | n \in \{0,1\}, m \in \{1,2\}\}\)
Wörter bestimmen
Bestimmen Sie die Wörter der folgenden Sprache:
\(L = \{ (b^ma)^lza | m \in \{0,1\}, l \in \{1,2,3\}\}\)
Abzählen mit Hilfe von Gödelnummern
Gödelnummern unterstützen abzählbare un-/endliche Mengen. Letzteres (abzählbar unendlich) ist mit einem einfachen Stellenwertsystem zur Basis der Anzahl der Elemente und des somit (zwangsweise) unendlichen Alphabets nicht möglich.
Z. B. ist die Primzahlzerlegung von 10 = 2 1 · 3 0 · 5 1. Somit gäbe es an der zweiten Stelle kein Zeichen was unsinnig ist.
Angenommen:
jedes in einer formalen Sprache geschriebenes Programm löst ein Problem
wir interpretieren dies als Berechnung einer Lösung
So sind dies verschwindend wenige lösbare Probleme verglichen schon mit der Reichhaltigkeit der reellen Zahlen im Intervall \((0,1)\).
Stellenwerte I
Gegeben sei das Alphabet \(\Sigma = \{a,gen,i,re\}\) mit Aufzählung in dieser Reihenfolge. Bestimmen Sie die Zahlen \(n\) nach Stellenwert mit Bild \(f (n)\) der Wörter \(regen\), \(aare\) und die Worte mit Stellenwert \(15\), \(118\).
Stellenwerte II
Gegeben sei das Alphabet \(\Sigma = \{e,h,r,ste\}\) mit Aufzählung in dieser Reihenfolge. Bestimmen Sie die Zahlen n nach Stellenwert mit Bild \(f (n)\) der Wörter \(steh\), \(rehe\) und die Worte mit Stellenwert \(45\), \(1417\).
Gödelnummern I
Gegeben sei das Alphabet \(\Sigma = \{e,l,ste,te\}\) mit Aufzählung in dieser Reihenfolge. Bestimmen Sie die Gödelnummer \(c(w)\) der Wörter \(este\), \(elle\) und die Worte mit Gödelnummer \(720\), \(12600\).
Gödelnummern II
Gegeben sei das Alphabet \(\Sigma = \{h,he,re,ste\}\) mit Aufzählung in dieser Reihenfolge. Bestimmen Sie die Gödelnummer \(c(w )\) der Wörter \(steh\), \(reste\) und die Worte mit Gödelnummer \(144\), \(1500\).
Gödelnummern und ChatGPT
Eine Befragung von ChatGPT zum Thema Gödelnummern ergab, dass ChatGPT vorgeschlagen hat allen Zeichen \(a \in \Sigma\) eine Primzahl zuzuordnen und dann für das Vorkommen eines Zeichens \(a\) an Stelle \(i\) den aktuellen Wert mit der Primzahl des Zeichens hoch \(i\) zu multiplizieren.
Bewerten Sie diesen Vorschlag.
bezieht sich auf die Existenz der Aufzählung als „berechenbare Funktion“,
bezieht sich auf die Existenz eines „Programms“, was aber hier äquivalent ist.
Die Übertragung der Eigenschaft der Aufzählbarkeit muss mit Angabe eines ausführbaren Algorithmus erfolgen.
So kann - wie bei der Aufzählung von \(\mathbb{Z}\) - bei der Vereinigung abwechselnd die eine oder die andere Aufzählung verwendet werden. Die Aufzählung der rationalen Zahlen kann nach dem vorgestellten Verfahren von Cantor erfolgen. Die gilt ggf. auch für das Produkt.
(Ein Beispiel für ein Entscheidbarkeitsproblem.)
Es ist wichtig, dass der Vergleich von \(w\) abwechselnd mit \(L\) und \(\bar{L}\) (aufsteigend) erfolgt, da wir sonst nicht nach einer endlichen Anzahl von Schritten garantiert zu einem Ergebnis kommen.
Ist \(L\) aufzählbar, doch \(\bar{L}\) nicht, so endet das Verfahren, genau dann wenn \(w \in L\) ist. Daher ist Wortproblem aufzählbarer Sprachen semi-entscheidbar.
Damit gilt:
rekursive bzw. entscheidbare Sprache ⇒ rekursiv aufzählbare Sprache
semi-entscheidbare Sprache ⇐ rekursiv aufzählbare Sprache
Das Collatz-Problem kann direkt in eine Collatz-Sprache über \(\Sigma _{\text{Zahl}}\) übertragen werden:
Das Wortproblem auf dieser Sprache ist damit — hier nach Definition des Problems statt einer Aufzählung — ebenso mindestens semi-entscheidbar.
Ob das Problem auch entscheidbar ist, konnte bisher niemand beantworten. Die naive Methode des Ausprobierens, ob es überhaupt ein \(w \in N\) mit \(w \notin L_{\text{Collatz}}\) gibt, hat trotz intensiver Suche bisher nicht geendet.
Collatz-Funktion
Die parametrisierte Collatz-Funktion \(f_{\alpha ,\beta }(n) : \mathbb{N} \rightarrow \mathbb{N}\) laute für \(\alpha ,\beta \in \mathbb{N}\):
Bestimmen Sie mit einem Programm das kleinste \(k \in \mathbb{N}\) für das \(f^k_{3,1}(27) = 1\) ist.
Sei die Sprache \(L_{\text{Collatz}_{3,7}} = \{n \in \mathbb{N} | \exists k \in \mathbb{N}_0 : f^k_{3,7}(n) = 1\}\).
Bestimmen Sie mit einem Programm die Menge \(M = \bar{L}_{3,7} \cap [1,20]\).
Rekursive Sprachen
Es seien \(L_1\) und \(L_2\) rekursive Sprachen über dem Alphabet \(\Sigma \). Sei \(L= L_1 \setminus L_2\).
Zeigen oder widerlegen Sie, dass \(L\) eine rekursive Sprache über \(\Sigma \) sei.
Ein Satz S wird mit diesen Regeln R gebildet:
Ein Satz besteht aus einer Substantivphrase und einer Verbphrase.
Eine Substantivphrase hat ein optionales Bestimmungswort und ein Substantiv.
Eine Verbphrase besteht aus optionalem Modalverb und einem Hauptverb.
Ein Bestimmungswort ist The oder One.
Ein Substantiv ist student oder professor.
Ein Modalverb ist should oder might.
Ein Hauptverb ist listen oder teach.
Darin wurden diese Variablen V und Symbole T verwendet:
{Satz, Substantivphrase, Verbphrase, Bestimmungswort, Substantiv, Modalverb, Hauptverb}
{The, One, student, professor, should, might, listen, teach}.
Die Regeln von Grammatiken werden auch Produktionen genannt
Eine Grammatik für boolesche Terme ist \(G_{\text{Logik}} = (V ,T ,R,S)\) mit
Eine Ableitung des Terms \(S \overset{*}{\Rightarrow } {\color{red}(a \wedge b) \vee c} \in L(G_\text{Logik})\) kann dann so ablaufen:
Regel |
|||||
|---|---|---|---|---|---|
S = Term |
|||||
r2.1 |
↧ |
||||
Term |
∨ |
Term |
|||
r1.4,r1.2 |
↧ |
↧ |
|||
(Term) |
∨ |
Variable |
|||
r2.2,r4 |
↧ |
↧ |
|||
( Term |
∧ |
Term ) |
∨ |
c |
|
r1.2,r1.2 |
↧ |
↧ |
|||
( Variable |
∧ |
Variable ) |
∨ |
c |
|
r4,r4 |
↧ |
↧ |
|||
( a |
∧ |
b ) |
∨ |
c |
Sprache bestimmen: ersw
Bestimmen Sie die Sprache \(L(G)\) für \(G = (V ,T ,R,S)\):
Sprache bestimmen: kot
Bestimmen Sie die Sprache \(L(G)\) für \(G = (V ,T ,R,S)\):
Wenn auf der linken Seite einer Regel ein komplexer Ausdruck steht, dann erfolgt die Ersetzung für den Ausdruck als Ganzes.
D. h. Sei das aktuelle Wort \(w = \text{C}tt\), dann wird \(w \overset{r_4}{\Rightarrow } \text{o|ok}\).
Ableitung finden: ewtiewet
Wie wird das Wort \(ewtiewet\) aus der Grammatik \(G = (V ,T ,R,S)\) abgeleitet?
Ableitung finden: etrrtse
Wie wird das Wort \(etrrtse\) aus der Grammatik \(G = (V ,T ,R,S)\) abgeleitet?
\(M_3 = \{0\}\cup \{1\}\times \{0,1\}^* = \{0,1,10,11,100,101,110,111,...\}= L(G )\):
\(M_2 = \{0^n1^n |n \in \mathbb{N}\}= \{01,0011,000111,...\}= L(G )\):
\(M_1 = \{0^n1^n2^n |n \in \mathbb{N}\}= \{012,001122,000111222,...\}= L(G )\):
Eine relevante Frage ist: Welches ist der höchste Grammatik-Typ einer erzeugten Sprache?
Umformulierung einer allgemeinen Regel zur Vertauschung von zwei Variablen in kontextsensitive Regeln (der Kontext ist hierbei nicht explizit definiert kann aber natürlich ergänzt werden):
Gegeben sei die Regel \(r_2 : \text{CB} \mapsto \text{BC}\).
Umformulierung in kontextsensitive Regeln:
In jeder Regel wird nur eine Variable ersetzt!
Chomsky-Typ: ikos
Bestimmen Sie den Chomsky-Typ der Grammatik \(G = (V ,T ,R,S)\) und geben Sie eine Ableitung für das Wort \(okoik\) an.
Chomsky-Typ: ru
Bestimmen Sie den Chomsky-Typ von \(G = (V ,T ,R,S)\) und die Sprache \(L(G)\):
Chomsky-Typ: iosu
Bestimmen Sie den Chomsky-Typ von \(G = (V ,T ,R,S)\) und die Sprache \(L(G)\):
Zur Erinnerung: Entscheidbare Sprachen sind aufzählbar.
Ist eine formale Sprache rekursiv aufzählbar, so wird sich daraus auch eine Typ-0 Grammatik erzeugen lassen.
(Aber) nicht jede Typ-0 Grammatik ist entscheidbar (d.h. rekursiv)!
Für eine Typ-0 Sprache des Halteproblems ist nur das positive entscheidbar.
Eine Endlosschleife endet - per Definition - nie...
Es muss auch sehr viele formale Sprachen geben, die nicht Typ-0 sind:
Typ-0 Sprachen sind durch Turingmaschinen erzeugbar, also aufzählbar.
Die Menge der formalen Sprachen ist überabzählbar...
Sind entscheidbare Sprache damit eine gute Wahl für Programmiersprachen?
Entscheidbarkeit sagt nichts über die Komplexität der Entscheidung aus.
Der Aufwand zur Analyse von Typ-1 Sprachen ist bereits sehr hoch.
Trotzdem haben viele Programmiersprachen Anteile, die kontextsensitiv sind:
der wesentliche Teil (insbesondere die Syntaxanalyse) ist jedoch kontextfrei
Sonderfälle (zum Beispiel Typprüfungen) werden gesondert verarbeitet
Aufzählung einer Sprache
Gegeben sei \(G = (V ,T ,R,S)\):
Gegeben Sei folgende Ableitung:
\(T \mapsto T \cdot T \mapsto ( T ) \cdot T \mapsto ( 1 ) \cdot T\)
Bestimmen Sie die Gödelnummer.
Bestimmen Sie die Ableitung/das Wort für die Gödelnummer \(n=37\,968\,750\,000\,000\).
Grammatiken für die wichtige Klasse der kontextfreien Sprachen sind nicht eindeutig:
Zwei Grammatiken für Terme wie \({\color{red}1+ 2 * 3} \in L(G1) = L(G2)\):
(E)BNF (Klassisch)
(a) Backus-Naur-Form (BNF) bzw. (b) erweiterte Backus-Naur-Form (EBNF), die die BNF um praktische Elemente erweitert.
PEG (Modern)
Parsing Expression Grammar (PEG)
Eine PEG definiert eine Reihenfolge zur Auflösung des Syntaxbaums. D. h. ein Umstellen der Regeln führt zu einer anderen Sprache. D. h. würde die Regel sum: sum "+" prod | prod in sum: prod | sum "+" prod geändert, würde sich die Sprache ändern bzw. manche Ausdrücke nicht mehr erkannt werden.
Nur selten werden erfolgreich neue allgemeine Programmiersprachen entwickelt.
Häufig(er) werden Domänenspezifische Sprachen (DSLs) entwickelt:
DSLs sind oft kontextfrei oder regulär.
DSLs befähigen Personen mit Domänenwissen, Programme in Ihrer Sprache zu entwickeln.
DSLs sind oft einfacher zu verstehen und zu verwenden als allgemeine Programmiersprachen.
DSLs haben oft große Einschränkungen sind dafür aber verständlicher
DSLs können oft einfacher optimiert werden, da sie weniger allgemein sind
Wir unterscheiden externe und interne DSLs.
Externe DSLs sind eigenständige Sprachen unabhängig von anderen Sprachen.
Zahlreiche Beispiele: SQL, Reguläre Ausdrücke, CSS, ...
Volle Kontrolle über Grammatik und Mächtigkeit
(Sehr viel) mehr Entwicklungsaufwand
Interne DSLs sind in einer anderen Sprache eingebettet und nutzen deren Syntax.
Prominents Beispiel: JSON
Es gibt Programmiersprachen, die gut (z. B. Scala) und solche die schlecht (z. B. Java) für die Entwicklung von internen DSLs geeignet sind.
Lark ist ein Python-Parser-Generator für kontextfreie Grammatiken.
LARK basiert auf EBNF
LARK unterstützt das Erstellen von Parse-Trees basierend auf der Grammatik.
Ein regulärer Ausdruck ist eine effiziente Darstellung von Sprachen.
Abfolgen und Alternativen
XY |
X nach Y |
X|Y |
X oder Y |
(X) |
Klammerung und Abfrage |
Zeichen
x |
Das Zeichen x |
\. |
Der Punkt . |
\t |
Tabulator |
\\\ |
Backslash \ |
Positionen
ˆ |
Anfang der Zeile |
$ |
Ende der Zeile |
\b |
Wortgrenze |
\B |
Nicht-Wortgrenze |
Mengen
. |
Beliebiges Zeichen |
[abc] |
Ein Zeichen aus Liste |
[ˆabc] |
Ein Zeichen außer aus Liste |
[a−r] |
Ein Zeichen aus Bereich |
\d |
Eine Ziffer [0−9] |
\D |
Keine Ziffer [ˆ0−9] |
\w |
Wortzeichen [a−zA−Z0−9_] |
Anzahl
X? |
einmal oder kein mal |
X* |
kein mal oder beliebig oft |
X+ |
einmal oder beliebig oft |
X{n} |
exakt n mal |
X{n,} |
mindestens n mal |
X{n,m} |
von n bis m mal |
X*? |
mit ? nicht gierig |
Regular Expressions werden in fast allen Programmiersprachen und IDEs zur Textanalyse und Transformation verwendet.
Es gibt leicht unterschiedliche Syntaxvarianten.
Fast alle Implementierungen bieten Erweiterungen, die über die klassischen regulären Sprachen hinausgehen. (z. B. Lookahead, Lookbehind, Charakterklassen...)
Bestimmung eines regulären Ausdrucks
Bestimmen Sie einen möglichst kurzen regulären Ausdruck \(\alpha \in \mathcal{R}(T)\), für den \(L(\alpha ) = L(G)\) für die Grammatik \(G = (V ,T ,R,S)\) gilt:
Rechts-lineare Grammatiken
Bestimmen Sie eine rechts-lineare Typ-3 Grammatik \(G = (V ,T ,R,S)\) für das Alphabet \(T = (e,r,s,t)\), für die \(L(G) = L(\alpha )\) mit \(\alpha = r((s|t)^*|e)^*\) gilt.
Links-lineare Grammatiken
Bestimmen Sie eine links-lineare Typ-3 Grammatik \(G = (V ,T ,R,S)\) für das Alphabet \(T = (a,b,k,n)\), für die \(L(G) = L(\alpha )\) mit \(\alpha = b^*an(k|a)^*\) gilt.
Regulären Ausdruck Vereinfachen
Vereinfachen Sie den regulären Ausdruck \(\alpha = (a^*b^*a^*|aba)^*(a|ac^*|aba)\) zu einem äquivalenten kürzeren Ausdruck β mit \(L(\alpha ) = L(\beta )\).
Konvertierung einer einfachen Markup Sprache mittels RegExps
Konvertieren Sie den verlinkten Text (https://delors.github.io/theo-algo-formale_sprachen/code/SomeText.txt) mittels mehrere regulärer Ausdrücke in HTML. Das HTML soll dann dem verlinkten Ergebnis entsprechen (https://delors.github.io/theo-algo-formale_sprachen/code/SomeText.html).
Beachten Sie, dass ggf. die Reihenfolge in der Sie die regulären Ausdrücke auswerten relevant sein kann.
Nutzen Sie ein Diff Tool Ihrer Wahl (zum Beispiel VS Code oder einfach diff), um zu überprüfen ob Ihr Ergebnis den Erwartungen entspricht.
Nutzen Sie entweder sed zur Auswertung Ihrer regulären Ausdrücke oder VS Code.
SED 101
sed ist ein Stream-Editor, der einzelne Textzeilen bearbeiten kann.
Um reguläre Ausdrücke zu verwenden, muss sed mit dem Flag -E gestartet werden. Z. B.: sed -E -f SomeTextToHTML.sed SomeText.txt > SomeText.html.
\s steht für alle "whitespace characters" (funktioniert aber ggf. nur unter bestimmten Versionen; z. B. nicht auf dem Mac); [ ] oder [[:space:]] sind eine Alternative.
Ein Ausdruck in sed hat die Form:
s/regexp/replacement/flags
Dabei wird der durch den regexp erkannte Text durch replacement ersetzt. Flags sind optional. Das g Flag (global) ermöglicht es alle Überstimmungen zu ersetzen und nicht nur die Erste.
Ein & im replacement bezieht sich auf den gesamten gefundenen Text.
Ein & im replacement kann durch ein Backslash escaped werden: \&.
\1, \2, \3 bezieht sich auf die gefundenen Gruppen (in Klammern) im regexp.
Ein sed Script ist eine Liste von sed Befehlen, die in einer Datei gespeichert werden und dann Zeile für Zeile auf den Input angewendet werden.
sed ist immer greedy und versucht längst-mögliche Übereinstimmungen zu finden. Ggf. ist es notwendig eine Formulierung zu finden, die verhindert, dass zu viel Text erfasst wird.
Beispiele
1$ echo "START aa B aa C aa ENDE START aa D aa" | sed -E 's/aa[^E]*aa/MATCH/'2START MATCH ENDE START aa D aa34$ echo "START aa B aa C aa ENDE START aa D aa" | sed -E 's/aa[^E]*aa/MATCH/g'5START MATCH ENDE START MATCH
DSL entwerfen mit LARK
Sie wollen eine DSL für Ihre eigene Markupsprache entwickeln. Ihr Ziel ist es Texte folgender Art zu parsen, um diese danach weiterzuverarbeiten.
+ Wer bin ich? Ich bin *Prof.* an der DHBW [link: www.dhbw-mannheim.de]. Meine Homepage finden sie hier: [link: www.michael-eichberg.de].
Ein „+“ am Anfang einer Zeile kennzeichnet eine Überschrift. Text in „*“ soll fett dargestellt werden. URLs stehen in Blöcken, die mit „[link:“ anfangen und mit „]“ enden.
Definieren Sie eine Grammatik in LARK. Wenn Sie reguläre Ausdrücke verwenden wollen – zum Beispiel zum Parsen von URLs – können Sie dies in der Grammatik direkt angeben (siehe WORD Regel). Der angehängte Code dient als Grundlage.
1from lark import Lark2GRAMMAR = r"""3s: ...45WORD: /[a-zA-Z]+/6%import common.WS_INLINE7%ignore WS_INLINE8"""910l = Lark(GRAMMAR, start="s")11print(l.parse("""+ Wer bin ich?"""))