Eine Sprache besteht aus Wörtern. Hierfür gibt es meistens Regeln, wie Wörter dieser Sprache gebildet werden, manchmal werden die Wörter aber auch explizit angegeben.
leere Sprache |
oder auch ![$L=\emptyset$](img16.png) |
Länge des Wortes |
Die Länge des Wortes ist die Anzahl der Symbole, die es aus umfaßt. |
Leeres Wort |
![$w_{\epsilon}=\epsilon$](img18.png) |
Inverses Wort |
![$w^{R}$](img19.png) |
Konkatenation:
![$L=L_{1}\circ L_{1}$](img20.png)
bedeutet (
![$w_{1}\in L_{1}$](img21.png)
,
![$w_{2}\in L_{2}$](img22.png)
)
![$w=w_{1}w_{2}$](img23.png)
.
Konkatenation läßt sich mehrfach wiederholen. Beispielsweise bedeutet
![$L^{n}$](img24.png)
n mal L:
Kleenabschluß: Unter dem Kleenabschluß versteht man
Für
steht für2
Fußnoten
- ... für2
- Genauso wie
, nur daß die Menge mit dem leeren Wort ausgeschlossen ist.