Deterministic finite automaton

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:

I want to see transducers and discussions of how these work, ASAP! Alec (talk) 23:58, 12 January 2018 (UTC)

• Source is "An Introduction to Formal Languages and Automata" - 4th edition, Peter Linz - great book.

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:

1. Acceptor-type automaton and
2. 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) 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"

See also

• NFAs
  • Equivalence of DFA-acceptors and NFA-acceptors