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:

• $A:\eq(Q,\Sigma,\delta,q_0,F)$ $\sum$ where:
  • $Q$ is a finite set of "states",
  • $\Sigma$ is the alphabet of the DFA, a finite set of symbols which may appear in "strings",
  • $\delta:Q\times\Sigma\rightarrow Q$ is a function, called the "transition function" and
  • $q_0\in Q$ is the "initial state" or "starting state" of the automaton

Acceptor-type

A tuple of 5 items:

• $A:\eq(Q,\Sigma,\delta,q_0,F)$ (or perhaps as an ordered pair: $A:\eq(A',F)$ for $A'$ the underlying DFA as described above) with terms exactly as above but with an additional item $F\in\mathcal{P}(Q)$ which is:
  • $F\subseteq Q$ is a set of "accepting states" or "final states"