Formale Sprachen und Grammatiken

• Grammatiken stellen Regel auf, nach denen die Wörter einer (formalen) Sprache gebildet werden.
• unterschiedliche Grammatiken können zur gleichen Sprache führen
• die Gesamtheit aller Wörter, die durch eine Grammatik gebildet werden können, heißt formale Sprache

Eine Grammatik ist definiert / festgelegt durch

• Menge der Terminalsymbole $\Sigma$ (= “Buchstaben”, d.h. Zeichen, aus denen die Wörter bestehen, Alphabet)
• Menge der Nichtterminalsymbole $N$ (Symbolen, die ersetzt werden müssen)
• Ersetzungsregeln (Produktionsregeln) $\delta$
• Startsymbol $S$

Beispiel: X-42

• Terminalsymbole $\Sigma =\{X,4,2\}$
• Nichtterminalsymbole $N=\{S,T\}$
• Produktionsregeln
  • $S\to TX|XT|TXT$
  • $T\to 2T4|4T2|24T|42T|T24|T42|24|42$
• Startsymbol S

Bsp.: 42X $S\to TX\to 42X$ (Ableitung)

Ableitungsbaum:

flowchart TD
	S --> T
	S --> X
	T --> 42

Aufgabe:

• Wort mit 7 Zeichen:
  • gültig: X222444 S ⇒ XT ⇒ X 2T4 ⇒ X22T44 ⇒ X222444

flowchart TD
S --> X
S --> T

T --> 2_1(2)
T --> T_1(T)
T --> 4_1(4)

T_1 --> 2_2(2)
T_1 --> T_2(T)
T_1 --> 4_2(4)

T_2(T) --> 2_3(2)
T_2(T) --> 4_3(4)

• ungültig: X2444, 22X, …