Informatik 12/13 (G9)

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.
====== Erzeugung formaler Sprachen ======
<WRAP center round info 80%>
Um festzulegen, welche Wörter zu einer Sprache gehören, formuliert man meist eine **Menge von Regeln (Syntax)**, nach denen alle Wörter der Sprache aus ihrem Alphabet gebildet werden können (**Produktionsregeln**). \\ 
Die Bildung eines Wortes mithilfe der Produktionsregeln nennt man seine **Ableitung**.
</WRAP>

===== Beispiel: Bezeichnung von Fernstraßen in Deutschland ====
Die [[https://de.wikipedia.org/wiki/Liste_der_Bundesautobahnen_in_Deutschland|Bezeichnungen aller Bundsstraßen und Autobahnen in Deutschland]] ist eine Sprache über dem Alphabet A = {A, B, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, die durch folgende **Produktionsregeln** ( = Syntax) definiert wird: 
<code>
  R1: Fernstraße = Autobahn
  R2: Fernstraße = Bundesstraße
  R3: Autobahn = "A"ZahlMaxDreistellig
  R4: Bundestraße = "B"ZahlMaxDreistellig
  R7: ZahlMaxDreistellig = Ziffer
  R6: ZahlMaxDreistellig = ZifferZiffer
  R8: ZahlMaxDreistellig = ZifferZifferZiffer
  R9: Ziffer = "1"
  R10: Ziffer = "2"
  R11: Ziffer = "3"
  R12: Ziffer = "4"
  R13: Ziffer = "5"
  R14: Ziffer = "6"
  R15: Ziffer = "7"
  R16: Ziffer = "8"
  R17: Ziffer = "9"
  R18: Ziffer = "0"
</code>
<WRAP center round info 80%>
**Begriffe:** \\
Kommt in den Produktionsregeln ein Element des Alphabets vor, so bezeichnet man es als **Terminal**, weil es sich im Verlauf der Ableitung eines Wortes nicht mehr ändert. Die Variablen ''Fernstraße'', ''Autobahn'', ... bezeichnet man als **Nichtterminale**, weil sie im Lauf der Ableitung noch ersetzt werden müssen.
 \\ \\ 
**Kurzschreibweise:** \\
Falls mehrere Produktionsregeln auf der linken Seite das selbe Nichtterminalsymbol haben, kann man sie mit Hilfe des Operators | ("oder") zu einer zusammenfassen. Die Regeln 9 - 18 oben kann man bspw. zusammenfassen zu \\ 
<code>
Ziffer = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" | "0" 
</code>
**Backus-Naur-Form** \\ 
Die oben beschriebene Form, mit der wir Produktionsregeln angeben können, bezeichnet man als [[https://de.wikipedia.org/wiki/Backus-Naur-Form|Backus-Naur-Form]] (**BNF**). Wir werden etwas später noch die [[https://de.wikipedia.org/wiki/Erweiterte_Backus-Naur-Form|erweiterte Backus-Naur-Form]] (**EBNF**) kennenlernen, die exakt gleich mächtig ist, jedoch in vielen Fällen eine kompaktere, griffigere Darstellung der Produktionen ermöglicht.

</WRAP>


===== Aufgabe 1 =====
Geben Sie die **Ableitungen** der Wörter "A34" und "B903" an und zeichnen Sie zur ersten der beiden Ableitungen einen **Ableitungsbaum**.

==== Lösung ====
$$Fernstraße\xrightarrow[]{(R1)}Autobahn\xrightarrow[]{(R3)}\mathrm{"A"}ZahlMaxDreistellig\xrightarrow[]{(R6)}\mathrm{"A"}Ziffer\ Ziffer$$
$$\xrightarrow[]{(R11)}\mathrm{"A3"}Ziffer\xrightarrow[]{(R12)}\mathrm{"A34"}Ziffer$$
 \\ \\ 
$$Fernstraße\xrightarrow[]{(R2)}Bundesstraße\xrightarrow[]{(R4)}\mathrm{"B"}ZahlMaxDreistellig\xrightarrow[]{(R8)}\mathrm{"B"}Ziffer\ Ziffer\ Ziffer$$
$$\xrightarrow[]{(R17)}\mathrm{"B9"}Ziffer\ Ziffer\xrightarrow[]{(R18)}\mathrm{"B90"}Ziffer\xrightarrow[]{(R11)}\mathrm{"B903"}$$

Zur ersten der beiden Ableitungen hier der **Ableitungsbaum**:
{{ :formalesprachen:pasted:20250714-145442.png?400 }}

===== Aufgabe 2 =====
Ist die Ableitung eines Wortes immer eindeutig? Begründen Sie Ihre Antwort beispielhaft mit den obigen Produktionsregeln!

<WRAP center round info 80%>
**Definition:** \\ \\
Eine **formale Grammatik**
$$G = (V, A, P, S)$$
besteht aus
  * der Menge der **Nichtterminale** $V$
  * dem **Alphabet** $A$
  * einer Menge von **Produktionsregeln** $P$ und
  * einem Startsymbol $S\in V$
Dabei müssen $A$ und $V$ disjunkt sein, d.h. $A \bigcap V = \{\}$. \\ 
$G$ definiert eine **formale Sprache**, die aus allen Wörtern aus $A^*$ besteht, die aus dem Startsymbol $S$ durch Anwendung endlich vieler Produktionsregeln aus $P$ abgeleitet werden können.
</WRAP>

===== Aufgabe 3 =====

a) Geben Sie eine Grammatik an, die Sprache beschreibt, in der deutsche Autokennzeichen notiert werden.
  * Die Sprache soll alle Autokennzeichen der Formen "ND WW 16" und "IN XE 312E"  beschreiben (Ortskürzel mit bis zu drei Buchstaben, Zwischenbereich mit bis zu zwei Buchstaben, ein- bis dreistellige Zahl, optional "E" am Ende).
  * Auch nichtexistente Ortskürzel dürfen vorkommen.
b) Geben Sie zur Grammatik aus a) die Ableitung des Kennzeichens "SOB AX 12E" an. \\ 

[[.aufgabe3loesung:start|Lösung]]
===== Rekursive Produktionsregeln =====
<WRAP center round info 80%>
Gegeben ist die Grammatik $G = (V, A, P, S)$ mit dem Alphabet $A=\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$, den Nichtterminalen $V=\{Zahl,\ Ziffer\}$, dem Startsymbol $S = Zahl$ und folgenden Produktionsregeln:
<code>
  R1: Zahl = Ziffer | Ziffer Zahl
  R2: Ziffer = "0" | "1" | ... | "9"
</code>
\\ \\ 
Beschreiben Sie die Semantik der erzeugten Sprache! Inwiefern sind diese Produktionsregeln rekursiv?
</WRAP>

===== Aufgabe 4 =====
Erweitern sie obige Grammatik G so, dass die Sprache genau die Dezimaldarstellungen aller ganzen Zahlen umfasst, wobei keine Vornullen erlaubt sein sollen.


===== Aufgabe 5 =====
Geben Sie eine Grammatik einer Sprache an, die alle ungeklammerten Terme enthält, die
  * nur die Rechenzeichen + und - sowie
  * als Operanden nur die Variablen a, b und c besitzen.

Gemeint sind also Terme der Form $a$, $b$, $c$, $a + b$, $a - b$, $a + b - c$, $a + a - b + b$ usw.

===== Aufgabe 6 ======
Die Sprache aller symmetrischen Wörter über den Alphabet $A = \{a, b\}$ enthält das leere Wort $\varepsilon$, die Wörter $a$, $b$, $aa$, $bb$, $aba$, usw. \\ \\ 
Geben Sie eine Grammatik an, die diese Sprache erzeugt.