leeres Wort
Substantiv · Wortverbindung · n
—
Theoretische Informatik, formale Sprachen: Zeichenkette, welche aus keinem Symbol besteht
Das leere Wort ist das neutrale Element der Konkatenation; es gilt also für beliebiges Wort w\,: w \varepsilon = \varepsilon w = w\,.
Das leere Wort \varepsilon \, taucht in formalen Grammatiken etwa auf, um löschende Ersetzungsregeln für Nichtterminale zu formulieren.
Die Grammatik aus den Terminalsymbolen \lbrace a,\,b \rbrace, den Nichtterminalsymbolen \lbrace S \rbrace\, (ein einziges) und den Ersetzungsregeln \lbrace S \rightarrow aSa, S \rightarrow bSb, S \rightarrow a, S \rightarrow b, S \rightarrow \varepsilon \rbrace sowie dem Startsymbol S\, erzeugt die Menge aller Palindrome über dem Alphabet \Sigma = \lbrace a, b \rbrace\,. Das leere Wort \varepsilon \, ist Element der von dieser Grammatik erzeugten Sprache.
leeres Wort
Deutsch » Deutsch
Hilfswort