Deterministic finite automaton

From Maths
Jump to: navigation, search
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:=(Q,Σ,δ,q0) where:
  • in an "acceptor" type there's another item, F, for FQ, 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[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 FP(Q) which is:
    • FQ is a set of "accepting states" or "final states"

Transducer-type

See also

Notes

  1. Jump up As I hope to make one, and they probably exist out there somewhere!

References