Difference between revisions of "Template:Formal languages and grammars"

From blackwiki
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   = Formal languages and grammars
+
| name = Formal languages and grammars
|title   = [[Automata theory]]: [[formal language]]s and [[formal grammar]]s
+
| title = [[Automata theory]]: [[formal language]]s and [[formal grammar]]s
|fullwidth = yes
+
| state = {{{state<includeonly>|autocollapse</includeonly>}}}
 +
| listclass = plainlist
  
|col1 = {{Navbox|child
+
  | col1header = [[Chomsky hierarchy]]
  |state = plain
+
  | col1style = text-align: center;
  |liststyle = text-align:center;
+
  | col1 =
  |title = [[Chomsky hierarchy]]
+
* Type-0
|list1 = Type-0
+
*
|list2 =
+
* Type-1
|list3 = Type-1
+
* —
|list4 =
+
* —
|list5 =
+
* —
|list6 = Type-2
+
*
|list7 =
+
*
|list8 =
+
* Type-2
|list9 = Type-3
+
*
|list10 =
+
*
}}
+
* Type-3
 +
*
 +
* —
  
|col2 = {{Navbox|child
+
  | col2header = [[Formal grammar|Grammars]]
|state = plain
+
  | col2 =
  |liststyle = text-align:center;
+
* [[Unrestricted grammar|Unrestricted]]
|title = [[Formal grammar|Grammars]]
+
* (no common name)
  |list1 = [[Unrestricted grammar|Unrestricted]]
+
* [[Context-sensitive grammar|Context-sensitive]]
|list2 = (no common name)
+
* <span style = "white-space:nowrap;">Positive [[range concatenation grammars|range concatenation]]</span>
|list3 = [[Context-sensitive grammar|Context-sensitive]]
+
* [[Indexed grammar|Indexed]]
|list4 = [[Indexed grammar|Indexed]]
+
* —
|list5 = [[Tree-adjoining grammar|Tree-adjoining]] etc.
+
* [[Linear context-free rewriting system]]s
|list6 = [[Context-free grammar|Context-free]]
+
* [[Tree-adjoining grammar|Tree-adjoining]]
|list7 = [[Deterministic context-free grammar|Deterministic context-free]]
+
* [[Context-free grammar|Context-free]]
|list8 = [[Nested word|Visibly pushdown]]
+
* [[Deterministic context-free grammar|Deterministic context-free]]
|list9 = [[Regular grammar|Regular]]
+
* [[Nested word|Visibly pushdown]]
|list10 =
+
* [[Regular grammar|Regular]]
}}
+
*
 +
* [[Non-recursive grammar|Non-recursive]]
  
|col3 = {{Navbox|child
+
  | col3header = [[Formal language|Languages]]
  |state = plain
+
  | col3 =
|liststyle = text-align:center;
+
* [[Recursively enumerable language|Recursively enumerable]]
|title = [[Formal language|Languages]]
+
* [[Recursive language|Decidable]]
  |list1 = [[Recursively enumerable language|Recursively enumerable]]
+
* [[Context-sensitive language|Context-sensitive]]
|list2 = [[Recursive language|Recursive]]
+
* <span style = "white-space:nowrap;">Positive [[Range concatenation language|range concatenation]]<sup>*</sup></span>
|list3 = [[Context-sensitive language|Context-sensitive]]
+
* [[Indexed language|Indexed]]<sup>*</sup>
|list4 = [[Indexed language|Indexed]]
+
* —
|list5 = [[Mildly context-sensitive language|Mildly context-sensitive]]
+
* [[Linear context-free rewriting language]]
|list6 = [[Context-free language|Context-free]]
+
* [[Tree-adjoining grammar|Tree-adjoining]]
|list7 = [[Deterministic context-free language|Deterministic context-free]]
+
* [[Context-free language|Context-free]]
|list8 = [[Nested word|Visibly pushdown]]
+
* [[Deterministic context-free language|Deterministic context-free]]
|list9 = [[Regular language|Regular]]
+
* [[Nested word|Visibly pushdown]]
|list10 = [[Star-free language|Star-free]]
+
* [[Regular language|Regular]]
}}
+
* [[Star-free language|Star-free]]
 +
* [[Finite language|Finite]]
  
|col4 = {{Navbox|child
+
  | col4header = [[Abstract machine]]s
  |state = plain
+
  | col4 =
|liststyle = text-align:center;
+
* [[Turing machine]]
|title = Minimal [[finite-state machine|automaton]]
+
* [[Machine that always halts|Decider]]
  |list1 = [[Turing machine]]
+
* [[Linear bounded automaton|Linear-bounded]]
|list2 = [[Machine that always halts|Decider]]
+
* [[PTIME]] Turing Machine
|list3 = [[Linear bounded automaton|Linear-bounded]]
+
* [[Nested stack automaton|Nested stack]]
|list4 = [[Nested stack automaton|Nested stack]]
+
* [[Thread automaton]]
|list5 = [[Embedded pushdown automaton|Embedded pushdown]]
+
* restricted [[Tree stack automaton]]
|list6 = [[Pushdown automaton|Nondeterministic pushdown]]
+
* [[Embedded pushdown automaton|Embedded pushdown]]
|list7 = [[Deterministic pushdown automaton|Deterministic pushdown]]
+
* [[Pushdown automaton|Nondeterministic pushdown]]
|list8 = [[Nested word|Visibly pushdown]]
+
* [[Deterministic pushdown automaton|Deterministic pushdown]]
|list9 = [[Finite-state machine|Finite]]
+
* [[Nested word|Visibly pushdown]]
|list10 = [[Aperiodic finite state automaton|Counter-free (with aperiodic finite monoid)]]
+
* [[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>
  
|below  = <small><span style="white-space:nowrap;">Each category of languages is a [[subset|proper subset]] of the category directly above it.</span> - <span style="white-space:nowrap;">Any automaton and any grammar in each category has an equivalent automaton or grammar in the category directly above it.</span></small>
 
 
}}<noinclude>
 
}}<noinclude>
[[Category:Automata theory]]
+
{{collapsible option}}
 
+
[[Category:Computer science navigational boxes]]
[[cs:Šablona:Formální jazyky a gramatiky]]
+
[[Category:Linguistics navigational boxes]]
[[de:Vorlage:Formale Sprachen und Grammatiken]]
 
[[hr:Predložak:Formalni jezici i gramatike]]
 
[[mk:Шаблон:Формални јазици и граматики]]
 
[[nn:Mal:Formelle språk og grammatikkar]]
 
[[sk:Šablóna:Formálne jazyky a gramatiky]]
 
[[sr:Шаблон:Formalni jezici i gramatike]]
 
[[fi:Malline:Formaalit kielet]]
 
 
</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}}
    • shows the template collapsed to the title bar if there is a {{navbar}}, a {{sidebar}}, or some other table on the page with the collapsible attribute
    • shows the template in its expanded state if there are no other collapsible items on the page

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.