Language Theory Foundations - Formal Definitions: Difference between revisions
Jump to navigation
Jump to search
Brodriguez (talk | contribs) (Add formal definition of DFA) |
Brodriguez (talk | contribs) (Add formal definition of PDA) |
||
| Line 36: | Line 36: | ||
== Formal Definition of DFA == | == Formal Definition of DFA == | ||
DFA's are defined as M, such that: | DFA's (Deterministic Finite Automata) are defined as M, such that: | ||
M = (Q, Σ, δ, q_0, F) | M = (Q, Σ, δ, q_0, F) | ||
| Line 43: | Line 43: | ||
* Σ - The alphabet of characters defined for the language that M describes. | * Σ - The alphabet of characters defined for the language that M describes. | ||
** Ex: {a, b, ..., z} | ** 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. | * δ - The transition function for M. | ||
** Ex: | ** Ex: | ||
Latest revision as of 04:25, 23 November 2019
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}