User:Jochen Burghardt/sandbox6
Jump to navigation
Jump to search
Chomsky hierarchy
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:
- LALR
- SLR
- Mildly_context-sensitive_language#Control Language Hierarchy
- regular tree languages (flattened to strings)
- automata from Template_talk:Formal_languages_and_grammars#Catagorisation of further automata where appropriate
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)
Chomsky hierarchy (Old)
| 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:
- LALR
- SLR
- Mildly_context-sensitive_language#Control Language Hierarchy
- regular tree languages (flattened to strings)
- automata from Template_talk:Formal_languages_and_grammars#Catagorisation of further automata where appropriate
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