Difference between revisions of "Deterministic finite automaton"
(Created page with "{{Stub page|grade=A**|msg=I want to see transducers and discussions of how these work, ASAP! ~~~~ * Source is "An Introduction to Formal Languages and Automata" - 4th edition...") |
m |
||
| Line 9: | Line 9: | ||
** {{M|\delta:Q\times\Sigma\rightarrow Q}} is a [[function]], called the "transition function" and | ** {{M|\delta:Q\times\Sigma\rightarrow Q}} is a [[function]], called the "transition function" and | ||
** {{M|q_0\in Q}} is the "initial state" or "starting state" of the automaton | ** {{M|q_0\in Q}} is the "initial state" or "starting state" of the automaton | ||
| + | There are two "defined" types: | ||
| + | # [[Acceptor-type automaton]] and | ||
| + | # [[Transducer-type automaton]] | ||
| + | In the practice of working with formal languages these terms are rarely used and DFAs are usually implicitly acceptors. In the wider practice of "programming" DFAs are a very useful model and are neither "pure" acceptors or transducers. DFAs and [[regex]] certainly do go hand in hand conceptually but (almost<ref group="Note">As I hope to make one, and they probably exist out there somewhere!</ref>) always do not use DFAs as their implementation as this wouldn't allow the implementation of more powerful features which programmers have become accustomed to. | ||
| + | |||
| + | I hope to explore deviations from DFAs without sacrificing the performance that comes from their determinism, for example adding a counter along certain transitions to allow "depth" of an expression. | ||
===[[Deterministic finite acceptor automaton|Acceptor-type]]=== | ===[[Deterministic finite acceptor automaton|Acceptor-type]]=== | ||
A tuple of 5 items: | A tuple of 5 items: | ||
| Line 14: | Line 20: | ||
** {{M|F\subseteq Q}} is a set of "accepting states" or "final states" | ** {{M|F\subseteq Q}} is a set of "accepting states" or "final states" | ||
===[[Deterministic finite transducer automaton|Transducer-type]]=== | ===[[Deterministic finite transducer automaton|Transducer-type]]=== | ||
| − | + | ==See also== | |
| + | * [[NFAs]] | ||
| + | ** [[Equivalence of DFA-acceptors and NFA-acceptors]] | ||
==Notes== | ==Notes== | ||
Revision as of 22:04, 13 January 2018
Definition
A deterministic finite automaton or DFA is a tuple of 4 items:
- A:=(Q,Σ,δ,q0,F) ∑ where:
- Q is a finite set of "states",
- Σ is the alphabet of the DFA, a finite set of symbols which may appear in "strings",
- δ:Q×Σ→Q is a function, called the "transition function" and
- q0∈Q is the "initial state" or "starting state" of the automaton
There are two "defined" types:
In the practice of working with formal languages these terms are rarely used and DFAs are usually implicitly acceptors. In the wider practice of "programming" DFAs are a very useful model and are neither "pure" acceptors or transducers. DFAs and regex certainly do go hand in hand conceptually but (almost[Note 1]) always do not use DFAs as their implementation as this wouldn't allow the implementation of more powerful features which programmers have become accustomed to.
I hope to explore deviations from DFAs without sacrificing the performance that comes from their determinism, for example adding a counter along certain transitions to allow "depth" of an expression.
Acceptor-type
A tuple of 5 items:
- A:=(Q,Σ,δ,q0,F) (or perhaps as an ordered pair: A:=(A′,F) for A′ the underlying DFA as described above) with terms exactly as above but with an additional item F∈P(Q) which is:
- F⊆Q is a set of "accepting states" or "final states"
Transducer-type
See also
Notes
- Jump up ↑ As I hope to make one, and they probably exist out there somewhere!
References
