Difference between revisions of "Deterministic finite automaton"

From Maths
Jump to: navigation, search
(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...")
 
m
Line 9: Line 9:
 
** {{M|\delta:Q\times\Sigma\rightarrow Q}} is a [[function]], called the "transition function" and
 
** {{M|\delta:Q\times\Sigma\rightarrow Q}} is a [[function]], called the "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
 +
There are two "defined" types:
 +
# [[Acceptor-type automaton]] and
 +
# [[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<ref group="Note">As I hope to make one, and they probably exist out there somewhere!</ref>) 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.
 
===[[Deterministic finite acceptor automaton|Acceptor-type]]===
 
===[[Deterministic finite acceptor automaton|Acceptor-type]]===
 
A tuple of 5 items:
 
A tuple of 5 items:
Line 14: Line 20:
 
** {{M|F\subseteq Q}} is a set of "accepting states" or "final states"
 
** {{M|F\subseteq Q}} is a set of "accepting states" or "final states"
 
===[[Deterministic finite transducer automaton|Transducer-type]]===
 
===[[Deterministic finite transducer automaton|Transducer-type]]===
 
+
==See also==
 +
* [[NFAs]]
 +
** [[Equivalence of DFA-acceptors and NFA-acceptors]]
  
 
==Notes==
 
==Notes==

Revision as of 22:04, 13 January 2018

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,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

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:

  • [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

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

References