Automata Theory, including abstract machines, grammars, parsing, grammatical inference, transducers, and finite-state techniques
Automata (plural of automaton) are abstract models of machines. These machines take an input such as a string of characters and give some output, often an "accept" or "decline" value.
These machines are closely related to formal-languages. Many languages can be categorized based on the type of automata that can accept them. For instance,
- regular languages can be recognized by some deterministic finite automata.
- context-free languages can be recognized by some pushdown automata.
- recursively enumerable languages can be recognized by some Turing machine.
There are many different types of automata, each with slightly different definitions. A few examples are
- Deterministic Finite Automata (DFA)
- Nondeterministic Finite Automata (NFA)
- Pushdown Automata
- Infinite Automata
- Alternating Automata
For instance, a deterministic finite automata $A$ has five parts:
- a finite set of states $Q$
- a finite set of input symbols called the alphabet $\Sigma$
- a transition function $\delta: (Q\times \Sigma)\rightarrow Q$
- an initial state $q_0 \in Q$
- a set of accept states $F\subseteq Q$
The automaton $A$ takes in a string $\sigma$ of characters of $\Sigma$. The automaton starts at state $q_0$ and then for each letter of $\sigma$ it moves to another state according to the transition function $\delta$. Once the automaton has used every letter of $\sigma$, if its final state is in $F$, then we say that $A$ accepts $\sigma$.
For questions also about
- formal languages, use formal-languages
- formal grammars, use formal-grammar
- context-free grammars, use context-free-grammar
- regular languages, use regular-language
- regular expressions, use regular-expressions
- Turing machines, use turing-machines
- the pumping lemmas, use pumping-lemma
- computability, use computability
