Difference between revisions of "Deterministic finite automaton"
m (Adding linked term) |
m (Removing f) |
||
| Line 4: | Line 4: | ||
==Definition== | ==Definition== | ||
A ''deterministic finite automaton'' or ''DFA'' is a [[tuple]] of 4 items: | A ''deterministic finite automaton'' or ''DFA'' is a [[tuple]] of 4 items: | ||
| − | * {{M|A:\eq(Q,\Sigma,\delta,q_0 | + | * {{M|A:\eq(Q,\Sigma,\delta,q_0)}} {{M|\sum}} where: |
** {{M|Q}} is a [[finite set]] of "states", | ** {{M|Q}} is a [[finite set]] of "states", | ||
** {{M|\Sigma}} is the {{link|alphabet|formal languages}} of the DFA, a [[finite set]] of symbols which may appear in "{{link|string|formal languages|s}}", | ** {{M|\Sigma}} is the {{link|alphabet|formal languages}} of the DFA, a [[finite set]] of symbols which may appear in "{{link|string|formal languages|s}}", | ||
** {{M|\delta:Q\times\Sigma\rightarrow Q}} is a [[function]], called the "[[state machine transition function|''transition function'']]" and | ** {{M|\delta:Q\times\Sigma\rightarrow Q}} is a [[function]], called the "[[state machine transition function|''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 | ||
| + | * in an "acceptor" type there's another item, {{M|F}}, for {{M|F\subseteq Q}}, the "final" or "accepting" states. | ||
There are two "defined" types: | There are two "defined" types: | ||
# [[Acceptor-type automaton]] and | # [[Acceptor-type automaton]] and | ||
Latest revision as of 03:23, 21 January 2018
Definition
A deterministic finite automaton or DFA is a tuple of 4 items:
- [ilmath]A:\eq(Q,\Sigma,\delta,q_0)[/ilmath] [ilmath]\sum[/ilmath] where:
- [ilmath]Q[/ilmath] is a finite set of "states",
- [ilmath]\Sigma[/ilmath] is the alphabet of the DFA, a finite set of symbols which may appear in "strings",
- [ilmath]\delta:Q\times\Sigma\rightarrow Q[/ilmath] is a function, called the "transition function" and
- [ilmath]q_0\in Q[/ilmath] is the "initial state" or "starting state" of the automaton
- in an "acceptor" type there's another item, [ilmath]F[/ilmath], for [ilmath]F\subseteq Q[/ilmath], the "final" or "accepting" states.
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:
- [ilmath]A:\eq(Q,\Sigma,\delta,q_0,F)[/ilmath] (or perhaps as an ordered pair: [ilmath]A:\eq(A',F)[/ilmath] for [ilmath]A'[/ilmath] the underlying DFA as described above) with terms exactly as above but with an additional item [ilmath]F\in\mathcal{P}(Q)[/ilmath] which is:
- [ilmath]F\subseteq Q[/ilmath] is a set of "accepting states" or "final states"
Transducer-type
See also
Notes
- ↑ As I hope to make one, and they probably exist out there somewhere!
References
