Language Theory Foundations - Formal Definitions

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)

Formal Definition of DFA

DFA's (Deterministic Finite Automata) are defined as M, such that:

M = (Q, Σ, δ, q_0, F)

• Q - All states defined within M.
  • Ex: {A, B, ..., Z}
• Σ - The alphabet of characters defined for the language that M describes.
  • Ex: {a, b, ..., z}
• δ - The transition function for M.
  • Ex:
• q_0 - The start state for M.
  • Ex: S
• F - All final states for M.
  • Ex: {B, C, ..., Z}

Formal Definition of PDA

PDA's (Pushdown Automata) are defined as M, such that:

M = (Q, Σ, Γ, δ, q_0, F)

• Q - All states defined within M.
  • Ex: {A, B, ..., Z}
• Σ - The alphabet of characters defined for the language that M describes.
  • Ex: {a, b, ..., z}
• Γ - The stack of states for M. Must be empty by the time the passed string is empty, or else the string is not valid.
  • Ex: {A, A, B, B, B, ..., Z}
• δ - The transition function for M.
  • Ex:
• q_0 - The start state for M.
  • Ex: S
• F - All final states for M.
  • Ex: {B, C, ..., Z}