Language Theory Foundations - Formal Definitions: Difference between revisions
Jump to navigation
Jump to search
Brodriguez (talk | contribs) (Create page) |
Brodriguez (talk | contribs) (Add formal definition of PDA) |
||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
Various formal definitions of Languages and Grammars related to "Language Theory Foundations". | 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. | 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. | ||
| Line 32: | Line 33: | ||
| Deterministic Finite Automata (DFA),<br>Non-Deterministic Finite Automata (NFA) | | Deterministic Finite Automata (DFA),<br>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} | |||
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}