Difference between revisions of "Template:Formal languages and grammars"
Jump to navigation
Jump to search
(Extra pair of parentheses caused an extra line break, making some rows in the chart to be offset incorrectly) |
imported>Uanfala (refine cat) |
||
| (72 intermediate revisions by 36 users not shown) | |||
| Line 1: | Line 1: | ||
{{Navbox with columns | {{Navbox with columns | ||
| − | |name | + | | name = Formal languages and grammars |
| − | |title | + | | title = [[Automata theory]]: [[formal language]]s and [[formal grammar]]s |
| − | | | + | | state = {{{state<includeonly>|autocollapse</includeonly>}}} |
| + | | listclass = plainlist | ||
| − | + | | col1header = [[Chomsky hierarchy]] | |
| − | | | + | | col1style = text-align: center; |
| − | | | + | | col1 = |
| − | | | + | * Type-0 |
| − | + | * — | |
| − | + | * Type-1 | |
| − | + | * — | |
| − | + | * — | |
| − | + | * — | |
| − | + | * — | |
| − | + | * — | |
| − | + | * Type-2 | |
| − | + | * — | |
| − | + | * — | |
| − | + | * Type-3 | |
| + | * — | ||
| + | * — | ||
| − | + | | col2header = [[Formal grammar|Grammars]] | |
| − | + | | col2 = | |
| − | | | + | * [[Unrestricted grammar|Unrestricted]] |
| − | + | * (no common name) | |
| − | | | + | * [[Context-sensitive grammar|Context-sensitive]] |
| − | + | * <span style = "white-space:nowrap;">Positive [[range concatenation grammars|range concatenation]]</span> | |
| − | + | * [[Indexed grammar|Indexed]] | |
| − | + | * — | |
| − | + | * [[Linear context-free rewriting system]]s | |
| − | + | * [[Tree-adjoining grammar|Tree-adjoining]] | |
| − | + | * [[Context-free grammar|Context-free]] | |
| − | + | * [[Deterministic context-free grammar|Deterministic context-free]] | |
| − | + | * [[Nested word|Visibly pushdown]] | |
| − | + | * [[Regular grammar|Regular]] | |
| − | + | * — | |
| + | * [[Non-recursive grammar|Non-recursive]] | ||
| − | + | | col3header = [[Formal language|Languages]] | |
| − | | | + | | col3 = |
| − | + | * [[Recursively enumerable language|Recursively enumerable]] | |
| − | + | * [[Recursive language|Decidable]] | |
| − | | | + | * [[Context-sensitive language|Context-sensitive]] |
| − | + | * <span style = "white-space:nowrap;">Positive [[Range concatenation language|range concatenation]]<sup>*</sup></span> | |
| − | + | * [[Indexed language|Indexed]]<sup>*</sup> | |
| − | + | * — | |
| − | + | * [[Linear context-free rewriting language]] | |
| − | + | * [[Tree-adjoining grammar|Tree-adjoining]] | |
| − | + | * [[Context-free language|Context-free]] | |
| − | + | * [[Deterministic context-free language|Deterministic context-free]] | |
| − | + | * [[Nested word|Visibly pushdown]] | |
| − | + | * [[Regular language|Regular]] | |
| − | + | * [[Star-free language|Star-free]] | |
| + | * [[Finite language|Finite]] | ||
| − | + | | col4header = [[Abstract machine]]s | |
| − | | | + | | col4 = |
| − | + | * [[Turing machine]] | |
| − | + | * [[Machine that always halts|Decider]] | |
| − | | | + | * [[Linear bounded automaton|Linear-bounded]] |
| − | + | * [[PTIME]] Turing Machine | |
| − | + | * [[Nested stack automaton|Nested stack]] | |
| − | + | * [[Thread automaton]] | |
| − | + | * restricted [[Tree stack automaton]] | |
| − | + | * [[Embedded pushdown automaton|Embedded pushdown]] | |
| − | + | * [[Pushdown automaton|Nondeterministic pushdown]] | |
| − | + | * [[Deterministic pushdown automaton|Deterministic pushdown]] | |
| − | + | * [[Nested word|Visibly pushdown]] | |
| − | + | * [[Finite-state machine|Finite]] | |
| − | + | * [[Aperiodic finite state automaton|Counter-free (with aperiodic finite monoid)]] | |
| + | * [[Deterministic acyclic finite state automaton|Acyclic finite]] | ||
| + | |||
| + | | below = <span style = "white-space:nowrap;">Each category of languages, except those marked by a <sup>*</sup>, is a [[proper subset]] of the category directly above it.</span> <span style = "white-space:nowrap;">Any language in each category is generated by a grammar and by an automaton in the category in the same line.</span> | ||
| − | |||
}}<noinclude> | }}<noinclude> | ||
| − | [[Category: | + | {{collapsible option}} |
| − | + | [[Category:Computer science navigational boxes]] | |
| − | [[ | + | [[Category:Linguistics navigational boxes]] |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
</noinclude> | </noinclude> | ||
Latest revision as of 23:17, 23 May 2019
Initial visibility: currently defaults to autocollapse
To set this template's initial visibility, the |state= parameter may be used:
|state=collapsed:{{Formal languages and grammars|state=collapsed}}to show the template collapsed, i.e., hidden apart from its title bar|state=expanded:{{Formal languages and grammars|state=expanded}}to show the template expanded, i.e., fully visible|state=autocollapse:{{Formal languages and grammars|state=autocollapse}}
If the |state= parameter in the template on this page is not set, the template's initial visibility is taken from the |default= parameter in the Collapsible option template. For the template on this page, that currently evaluates to autocollapse.