Jump to content

User:Jochen Burghardt/sandbox6

From Wikipedia, the free encyclopedia
Ch0 Dec Ch1 Ind Thr Lcr Tag Ch2 Uam Dpa New ... Ll3 Ll2 Ll1 Ll0 Lin Ch3 Sfl Fin Pat Slg
  Unrestricted grammar
≡ Chomsky type-0 grammar
Recursively enumerable language
Turing machine
Ch0
  Decidable language
Decider
Dec . .
  Context-sensitive grammar
≡ Chomsky type-1 grammar
Linear bounded automaton
Ch1 . .
  Indexed grammar
Nested stack automaton
Ind . .
  Thread automaton Thr .
  Linear context-free rewriting system
Minimalist grammar
Simple range concatenation grammar
Lcr .
  Tree-adjoining grammar
Linear indexed grammar
Combinatory categorial grammar
Head grammar
Embedded pushdown automaton
Tag .
  Context-free grammar
≡ Chomsky type-2 grammar
Noncontracting grammar
Nondeterministic pushdown automaton
Ch2
  Unambiguous context-free grammar Uam
  Deterministic pushdown automaton
LR(k) grammar for any k≥1
Dpa
  Nested word grammar New . . . .
  ...
  LL(3) Ll3
  LL(2) Ll2
  LL(1)
Simple deterministic languages
Ll1
  LL(0) Ll0 . . . .
  Linear grammar Lin
  Regular grammar
≡ Chomsky type-3 grammar
Finite-state machine
Regular expression
Ch3
  Star-free language
Aperiodic finite state automaton
Sfl
  Non-recursive grammar
Finite language
Deterministic acyclic finite automaton
Fin
  Pattern language Pat
  Straight-line grammar
Singleton language
Slg

Legend:

Language classes are weakly equivalent. Click on symbol for source or proof.
The table row's class is a proper superset of the column's. Click on symbol for source or proof.
The table row's class is a proper superset of the column's. This follows from transitivity of ⊋.
The row's and the column's class are incomparable. Click on symbol for source or proof.
The row's and the column's class are incomparable. This follows from transitivity of ⊋.
. The relation between row's and column's class still needs to be established.
  Mildly context sensitive language classes

To be inserted:

known relations:

  • according to SLR grammar#lead: LR(0) ⊆ SLR ⊆ LALR(1) and SLR ⊆ LR(1)
  • according to LL grammar#References/Beatty, J.C. (1982): p-reduced LL(1) ⊆ LALR(1) and Λ-free LL(1) ⊆ SLR(1)
  • according to LALR#LL parsers: LL(j) \ LALR(k) ≠ {} ≠ LALR(k) \ LL(j) for every j,k > 0 and it is undecidable whether a given LL(1) grammar is LALR(k) for any k≥0
  • according to LR_parser#Theory: LR(0) = (deterministic context-free) ∩ (prefix property)



  Unrestricted grammar
≡ Chomsky type-0 grammar
Recursively enumerable language
Turing machine
Decidable language
Decider
Context-sensitive grammar
≡ Chomsky type-1 grammar
Linear bounded automaton
Indexed grammar
Nested stack automaton
Tree-adjoining grammar
Linear indexed grammar
Combinatory categorial grammar
Head grammar
Embedded pushdown automaton
Context-free grammar
≡ Chomsky type-2 grammar
Noncontracting grammar
Nondeterministic pushdown automaton
Unambiguous context-free grammar
Deterministic pushdown automaton
LR(k) grammar for any k≥1
Nested word grammar
Regular grammar
≡ Chomsky type-3 grammar
Finite-state machine
Regular expression
Star-free language
Aperiodic finite state automaton
Non-recursive grammar
Finite language
Deterministic acyclic finite automaton
Straight-line grammar
Singleton language
  Unrestricted grammar  
Thread automaton
Linear context-free rewriting system
Minimalist grammar
Simple range concatenation grammar
Tree-adjoining grammar
  Indexed grammar  
Pattern language
Straight-line grammar
  Deterministic pushdown automaton  
...
LL(3)
LL(2)
LL(1)
Simple deterministic languages
LL(0)
  LL(1)  
Regular grammar


Legend:

Language classes in a table cell are weakly equivalent.

Mildly context sensitive language classes

To be inserted:

known relations:

  • according to SLR grammar#lead: LR(0) ⊆ SLR ⊆ LALR(1) and SLR ⊆ LR(1)
  • according to LL grammar#References/Beatty, J.C. (1982): p-reduced LL(1) ⊆ LALR(1) and Λ-free LL(1) ⊆ SLR(1)
  • according to LALR#LL parsers: LL(j) \ LALR(k) ≠ {} ≠ LALR(k) \ LL(j) for every j,k > 0 and it is undecidable whether a given LL(1) grammar is LALR(k) for any k≥0


References

[edit]