Language Theory Foundations - Formal Definitions

From Dev Wiki
Revision as of 04:15, 23 November 2019 by Brodriguez (talk | contribs) (Create page)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Various formal definitions of Languages and Grammars related to "Language Theory Foundations". This page may not make a lot of sense on its own, but can be useful to reference in the context of pretty much all other topics of Language Theory.

The Chomsky Hierarchy

The following table describes the four levels of "Formal Languages".

Note that each row is technically a subset of all rows prior.
That is, Type-0 technically includes Type-1, Type-2, and Type-3.
Type-1 technically includes Type-2 and Type-3.
And type-2 technically includes type-3.

Grammars Languages Accepting Machines
Type-0 Grammars,
Phase-StructureGrammars,
Unrestricted Grammars 		Recursively Enumerable Turning Machines,
Non-Deterministic Turning Machines
Type-1 Grammars,
Context-Sensitive Grammars,
Non-Contracting 		Context-Sensitive Linear-Bounded Automata
Type-2 Grammars,
Context-Free Grammars (CFG) 		Context-Free Pushdown Automata (PDA)
Type-3 Grammars,
Regular Grammars,
Left-Linear Grammars,
Right-Linear Grammars, 		Regular Deterministic Finite Automata (DFA),
Non-Deterministic Finite Automata (NFA)
Retrieved from "https://wiki.brandon-rodriguez.com/index.php?title=Language_Theory_Foundations_-_Formal_Definitions&oldid=84"