Benutzer:Jaleks/Playground
TheoInf
Chomsky-Hierarchie
http://csustan.csustan.edu/~tom/Lecture-Notes/Computation/Chomsky-hierarchy.jpg
Von Chomsky-Hierarchie#Übersicht
Grammatik | Sprachen | Automaten | Problementscheidbarkeit | Abgeschlossenheit | Regeln | Zeitabschätzung |
---|---|---|---|---|---|---|
Typ-3, regulär, eindeutige immer möglich | regulär | Endlicher Automat (egal ob deterministisch) | Wort-, Leerheits-, (Un-)endlichkeits- Problem, Gleichheit | (rechtsregulär) oder (linksregulär) , | ||
Typ-2, kontextfrei, eindeutige nicht immer möglich | kontextfrei | LR(k)-Automat / DPDA (determ. Kellerautomat) | Gleichheit plus wie bei PDA: | shift: qa ::= aq für alle reduce: rq ::= Aq für alle A ::= | ||
PDA (nichtdeterm. Kellerautomat) | Wort-, Leerheits-, (Un-)endlichkeits- Problem | |||||
Typ-1, kontextsensitiv | kontextsensitiv | LBA: linear platzbeschränkte nichtdeterministische Turingmaschine | Wortproblem | ist erlaubt, wenn es keine Regel in gibt. | ||
Typ-0, formal | rekursiv aufzählbar | Turingmaschine (egal ob deterministisch) | – | n.m. |
- Anmerkungen zur Tabelle
- Typ-0: rekursiv aufzählbar: nicht „nur“ rekursiv, die wären entscheidbar und damit abgeschlossen gegen Komplement
- LR(k): Zeitabschätzung linear, da jederzeit über Parsetabelle möglich
- Legende für die Spalte Regeln
- endliches Alphabet (Menge der Terminalsymbole)
- Menge der Nichtterminalsymbole/Hilfssymbole
- Startsymbol
- leeres Wort
- Menge von Produktionsregeln
- … Mengen-Differenzbildung
- … Kleenescher Abschluss
- … muss mindestens ein Symbol (also ein Terminal oder ein Nichtterminal) enthalten
In der obigen Tabelle werden somit mit deutschen/lateinischen Großbuchstaben Nichtterminalsymbole dargestellt (), mit deutschen/lateinischen Kleinbuchstaben Terminalsymbole () und griechische Kleinbuchstaben werden verwendet, wenn es sich sowohl um Nichtterminal als auch um Terminalsymbole handeln kann. (Achtung bei und : ein griechischer Kleinbuchstaben kann somit für mehrere Terminal- oder Nichtterminalsymbole stehen!)
- Legende für die Spalte Abgeschlossenheit
Die folgende Tabelle listet auf der Grundlage der 50-Laute-Tafel alle Hiragana und ihre Transkription nach dem Hepburn-System auf.
a | i | u | e | o | ya | yu | yo | |
---|---|---|---|---|---|---|---|---|
Einzelgraphen (Gojūon) | Digraphen (Yōon) | |||||||
∅ | あ a | い i | う u | え e | お o | |||
k | か ka | き ki | く ku | け ke | こ ko | きゃ kya | きゅ kyu | きょ kyo |
s | さ sa | し shi | す su | せ se | そ so | しゃ sha | しゅ shu | しょ sho |
t | た ta | ち chi | つ tsu | て te | と to | ちゃ cha | ちゅ chu | ちょ cho |
n | な na | に ni | ぬ nu | ね ne | の no | にゃ nya | にゅ nyu | にょ nyo |
h | は ha | ひ hi | ふ fu | へ he | ほ ho | ひゃ hya | ひゅ hyu | ひょ hyo |
m | ま ma | み mi | む mu | め me | も mo | みゃ mya | みゅ myu | みょ myo |
y | や ya | ゆ yu | よ yo | |||||
r | ら ra | り ri | る ru | れ re | ろ ro | りゃ rya | りゅ ryu | りょ ryo |
w | わ wa | (ゐ i/wi)* | (ゑ e/we)* | を wo | ||||
* | ん n | |||||||
Einzelgraphen mit Diakritika (Gojūon mit Dakuten und Handakuten) | Digraphen mit Diakritika (Yōon mit Dakuten und Handakuten) | |||||||
g | が ga | ぎ gi | ぐ gu | げ ge | ご go | ぎゃ gya | ぎゅ gyu | ぎょ gyo |
z | ざ za | じ ji | ず zu | ぜ ze | ぞ zo | じゃ ja | じゅ ju | じょ jo |
d | だ da | ぢ ji/dji | づ zu/dzu | で de | ど do | ぢゃ (ja) | ぢゅ (ju) | ぢょ (jo) |
b | ば ba | び bi | ぶ bu | べ be | ぼ bo | びゃ bya | びゅ byu | びょ byo |
p | ぱ pa | ぴ pi | ぷ pu | ぺ pe | ぽ po | ぴゃ pya | ぴゅ pyu | ぴょ pyo |
Die Schreibung てぃ für ti (im Gegensatz zu ち chi) kommt bei der Schreibung von Fremdwörtern in Katakana (ティ) des Öfteren vor, bei Hiragana nur in Ausnahmefällen.
* Diese Hiragana-Silben (wi und we) sind veraltet und werden heute nicht mehr verwendet.[1]