Language Theory Foundations - Formal Definitions - Revision history

Brodriguez: Add formal definition of PDA

2019-11-23T04:25:34Z

Add formal definition of PDA

@@ Line 36: / Line 36: @@
 == 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)
@@ Line 43: / Line 43: @@
 * Σ - The alphabet of characters defined for the language that M describes.
 ** Ex: {a, b, ..., z}
 * δ - The transition function for M.
 ** Ex:

Brodriguez: Add formal definition of DFA

2019-11-23T04:22:37Z

Add formal definition of DFA

@@ Line 1: / Line 1: @@
 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.
@@ Line 32: / Line 33: @@
 | Deterministic Finite Automata (DFA),<br>Non-Deterministic Finite Automata (NFA)
 |}

Brodriguez: Create page

2019-11-23T04:15:11Z

Create page

New page

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.

{| class="wikitable"
|-
! 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)
|}