Benutzer:Jaleks/Playground

TheoInf

Chomsky-Hierarchie

http://csustan.csustan.edu/~tom/Lecture-Notes/Computation/Chomsky-hierarchy.jpg

---

Von Chomsky-Hierarchie#Übersicht

Grammatik	Sprachen	Automaten	Problem­entscheid­barkeit	Abge­schlos­senheit	Regeln	Zeitab­schätz­ung
Typ-3, regulär, eindeutige immer möglich	regulär	Endlicher Automat (egal ob deterministisch)	Wort-, Leerheits-, (Un-)endlichkeits- Problem, Gleichheit	$\circ ,\ast ,\cup ,\cap ,\complement$	$A\rightarrow aB$ (rechtsregulär) oder $A\rightarrow Ba$ (linksregulär) $A\rightarrow a$, $A\rightarrow \varepsilon$ $A,B\in \Phi ,a\in \Sigma$	$O(n)$
Typ-2, kontextfrei, eindeutige nicht immer möglich	kontextfrei	LR(k)-Automat / DPDA (determ. Kellerautomat)	Gleichheit plus wie bei PDA:	$\circ ,\ast ,\complement$	shift: qa ::= aq für alle $a\in \Sigma$ reduce: rq ::= Aq für alle A ::= $r\in R$	$O(n)$
		PDA (nichtdeterm. Kellerautomat)	Wort-, Leerheits-, (Un-)endlichkeits- Problem	$\circ ,\ast ,\cup$	$A\rightarrow \gamma$ $A\in \Phi ,\gamma \in (\Sigma \cup \Phi )^{\ast }$	$O(n^{3})$
Typ-1, kontextsensitiv	kontextsensitiv	LBA: linear platzbeschränkte nichtdeterministische Turingmaschine	Wortproblem	$\circ ,\ast ,\cup ,\cap ,\complement$	$\alpha A\beta \rightarrow \alpha \gamma \beta$ $A\in \Phi ,\alpha ,\beta \in (\Sigma \cup \Phi )^{\ast },\gamma \in (\Sigma \cup \Phi )^{+}\;$ $S\rightarrow \varepsilon$ ist erlaubt, wenn es keine Regel $\alpha \rightarrow \beta S\gamma$ in $R$ gibt.	$2^{O(n)}$
Typ-0, formal	rekursiv aufzählbar	Turingmaschine (egal ob deterministisch)	–	$\circ ,\ast ,\cup ,\cap ,\exists$	$\alpha \rightarrow \beta$ $\alpha \in (\Sigma \cup \Phi )^{*}\setminus \Sigma ^{*},\beta \in (\Sigma \cup \Phi )^{\ast }$	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

• $\Sigma$ endliches Alphabet (Menge der Terminalsymbole)
• $\Phi$ Menge der Nichtterminalsymbole/Hilfssymbole
• $S\in \Phi$ Startsymbol
• $\varepsilon$ leeres Wort
• $R$ Menge von Produktionsregeln
• $\setminus$ … Mengen-Differenzbildung
• $\ast$ … Kleenescher Abschluss
• $\gamma \in (\Sigma \cup \Phi )^{+}$ … $\gamma$ muss mindestens ein Symbol (also ein Terminal oder ein Nichtterminal) enthalten

In der obigen Tabelle werden somit mit deutschen/lateinischen Großbuchstaben Nichtterminalsymbole dargestellt ($A,B\in \Phi$), mit deutschen/lateinischen Kleinbuchstaben Terminalsymbole ($a\in \Sigma$) und griechische Kleinbuchstaben werden verwendet, wenn es sich sowohl um Nichtterminal als auch um Terminalsymbole handeln kann. (Achtung bei $\ast$ und $^{+}$: ein griechischer Kleinbuchstaben kann somit für mehrere Terminal- oder Nichtterminalsymbole stehen!)

Legende für die Spalte Abgeschlossenheit

• $\circ$ … Konkatenation
• $\ast$ … Kleenescher Abschluss
• $\cup$ … Vereinigungsmenge
• $\cap$ … Schnittmenge
• $\complement$ … Komplementbildung

Hiragana#Tabelle_aller_Hiragana-Silben

Die folgende Tabelle listet auf der Grundlage der 50-Laute-Tafel alle Hiragana und ihre Transkription nach dem Hepburn-System auf.

0 0	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.