Autómata finito determinista

Autómata finito determinista que reconoce el lenguaje regular conformado exclusivamente por las cadenas con un número par de ceros y un número par de unos.
Ejemplo de AFD con dos estados. En nodo de la izquierda es inicial y de aceptación.

Un autómata finito determinista (abreviado AFD) es un autómata finito que además es un sistema determinista; es decir, para cada estado en que se encuentre el autómata, y con cualquier símbolo del alfabeto leído, existe siempre a lo más una transición posible desde ese estado y con ese símbolo.

Definición formal

Formalmente, se define como una 5-tupla (Q, Σ, q0, δ, F) donde:[1]

En un AFD no pueden darse ninguno de estos dos casos:

Véase también

Referencias

  1. Chakraborty, Samarjit (17 de marzo de 2003). «Formal Languages and Automata Theory. Regular Expressions and Finite Automata». Computer Engineering and Networks Laboratory. Swiss Federal Institute of Technology (ETH) Zürich (en inglés): 17. Consultado el 30 de marzo de 2010.
This article is issued from Wikipedia - version of the Tuesday, February 17, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.