0
Ich habe diese Liste von Formalismen und ich muss sie nach ihrer Ausdruckskraft ordnen, auch einer von ihnen gehört nicht wirklich dazu.Welcher Formalismus gehört nicht und welche sind stärker/gleich
Context-free Grammar(CFG)
Deterministic Finite Automata(DFA)
Deterministic Pushdown Automata(DPDA)
LR(0) Grammar
LR(1) Grammar
Nondeterministic Finite Automata(NFA)
Nondeterministic Finite Automata with epsilon transitions(NFAe)
Nondeterministic Turing MAchines(NTM)
Pushdown Automata(PDA)
Regular expressions(reg.exp)
Turing Machines(TM)
Turing MAchines with twi heads(TM2h)
Ich habe sie auf folgende Weise bestellt:
1. NFAe, NFA, DFA, reg.exp
2. DPDA
3. PDA, CFG
4. TM, TM2h, NTM
, wo diejenigen, die in 4 sind die mächtigsten. und ich entfernte LR-Grammatiken, weil sie nur eine Art sind, CFGs zu schreiben, so dass sie von einem LR-Parser geparst werden können.
Allerdings bin ich nicht sicher, ob das korrekt ist oder nicht.
LR (1) Grammatiken sind eine Teilmenge von kontextfreien Grammatiken und LR (0) Grammatiken sind eine Teilmenge von LR (1) Grammatiken. Eine Sprache ist LR (0) resp. LR (1) wenn LR (0) bzw. LR (1) Grammatik dafür. Ob eine solche Grammatik existiert, ist unentscheidbar, aber es ist leicht zu beweisen, dass für jedes "k" Nicht-LR (k) -Sprachen existieren. – rici