Deterministic finite automaton
From Maths
Revision as of 23:58, 12 January 2018 by Alec (Talk | contribs) (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...")
Stub grade: A**
This page is a stub
This page is a stub, so it contains little or minimal information and is on a to-do list for being expanded.The message provided is:
Definition
A deterministic finite automaton or DFA is a tuple of 4 items:
- [ilmath]A:\eq(Q,\Sigma,\delta,q_0,F)[/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
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
Notes
References
