Benutzer:Jaleks/Playground

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Chomsky-Hierarchie

[Bearbeiten | Quelltext bearbeiten]

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

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.[1]

  1. „Although kana for wi and we exist, namely hiragana ゐ and ゑ, and katakana ヰ and ヱ, they are not used in modern Japanese writing. These kana exist because the sounds they represent existed in Japanese at the time the kana were created.“ [1]