|
Dies sind Sprachen mit einer Typ-0-Grammatik.
2.1 Typ-0-Grammatik
Dies ist eine Grammatik ohne Einschränkungen.
\"u ® v aus P gilt: u Î (T È N)+ = (T È N)* {e}, v Î (T È N)*
Die beiden damit verknüpften Forderungen sind die, daß auf der linken Seite mindestens ein Nichtterminalsymbol stehen muß und u nicht das leere Wort e ist.
2.2 Beispiel
Die folgende Grammatik erzeugt die Sprache L(G)={ai ½ mit i als positive Zweierpotenz}
G=(T, N, P, S)
G=({S, A, B, C, D, E},{a}, P, S)
P={S ® ACaB, aD ® Da, Ca ® aaC, AD ® AC, CB ® DB, aE ® Ea, CB ® E, AE ® e}
Bsp.:
S ® ACaB ® AaaCB ® AaaE ® aa(e) = aa
2.3 Turingmaschine
Eine Turingmaschine akzeptiert Sprachen die nach einer Typ-0-Grammatik gebildet werden.
Eine Turingmaschine ist ein 7-Tupel T = (X,B,Z,d,b,z0,ZE), wobei gilt:
- X ist eine nichtleere, endliche Menge, das Eingabealphabet,
- B Ê X ist eine nichtleere, endliche Menge, das Bandalphabet,
- Z ist eine nichtleere, endliche Menge, die Zustandsmenge,
- d: (ZZE) x B ® B x {L,N,R} x Z ist eine Funktion, die Überführungsfunktion, welche jedem Paar(Zustand, gelesenen Zeichen) ein Tripel (zu schreibendes Zeichen, Kopfbewegung, Folgezustand) zuordnet,
- b Î BX ist das Leerzeichen oder Blank,
- z0 Î Z ist der Anfangszustand,
- ZE Í Z ist die Endzustandsmenge
|
