Quelltext der Seite formale Sprache

== Beispiele ==
# Die [[Programmiersprache]] [[C (Programmiersprache)|C]] ist eine formale Sprache. Die Wörter von C sind die jeweiligen Programme. Das Alphabet von C sind die [[Schlüsselwort (Programmierung)|Schlüsselwörter]] und Zeichen, die in der Definition von C festgelegt sind.
# Die natürlichen Zahlen in unärer Darstellung: <math>\mathbb{N}_{\rm un} := \{\varepsilon,1,11,111,1111,\ldots \}</math>
# Die unäre Sprache über <math>\{a\}</math>, die nur Wörter quadratischer Länge enthält: <math>{\rm quad\_count} := \{ a^{(n^2)} \mid n\in\mathbb N\}</math>
# Die Sprache, die <math>n</math> <math>a</math>s gefolgt von <math>n</math> <math>b</math>s enthält: <math>{\rm count}_2 := \{ a^nb^n \mid n\in\mathbb N\}</math>
# Die Sprache, die <math>n</math> <math>a</math>s gefolgt von <math>n</math> <math>b</math>s gefolgt von <math>n</math> <math>c</math>s enthält: <math>{\rm count}_3 := \{ a^nb^nc^n \mid n\in\mathbb N\}</math>
# Die Sprache aller [[Palindrom (Theoretische Informatik)|Palindrome]]: <math>{\rm pal} := \{w \in \{0,1\}^* \mid w=w^R \}</math>, wobei <math>w^R</math> die [[Spiegelung (Wort)|Spiegelung]] des Wortes <math>w</math> ist.
# Die Dezimalkodierung der Primzahlen: <math>{\rm prim}_{\rm dec} := \{{\rm dec}(p) \mid p \in {\rm PRIM} \}</math>. <br /> Hierbei bezeichnet <math>{\rm dec}\colon \mathbb{N} \rightarrow \{0,1,2,3,4,5,6,7,8,9\}^*</math> die Kodierung der natürlichen Zahlen im [[Dezimalsystem]] und PRIM steht für die Menge der [[Primzahl]]en.
# Die [[Morsefolge|Morse-]] oder [[Morsefolge|Thue-Folge]]: <math>{\rm thue} := \{ h^n_t(0) \mid n\in\mathbb{N} \}</math>, <br /> wobei <math>h_t</math> ein [[Homomorphismus]] ist, der folgendermaßen definiert ist: <math>h_t(\varepsilon)=\varepsilon</math> und <math>h_t(w0):= h_t(w)01</math>, <math>h_t(w1):= h_t(w)10</math>. <br /> Somit sind die ersten Elemente der Thue-Folge: 0, 01, 0110, 01101001, 0110100110010110 …