Autómata finito determinista

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:

  • Que existan dos transiciones del tipo δ(q,a)=q1 y δ(q,a)=q2, siendo q1q2;
  • Que existan transiciones del tipo δ(q, ε), donde ε es la cadena vacía, salvo que q sea un estado final, sin transiciones hacia otros estados.

Véase también

  • Autómata finito
  • Autómata finito no determinista
  • Trie, un ejemplo de autómata finito determinista.

Referencias

  1. Chakraborty, Samarjit (17 de marzo de 2003). «Formal Languages and Automata Theory. Regular Expressions and Finite Automata» (en inglés). Computer Engineering and Networks Laboratory. Swiss Federal Institute of Technology (ETH) Zürich:  pp. 17. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.89.9977. Consultado el 30 de marzo de 2010. 

Wikimedia foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Mira otros diccionarios:

  • Autómata finito — Un autómata finito (AF) o máquina de estado finito es un modelo matemático que realiza cómputos en forma automática sobre una entrada para producir una salida. Este modelo está conformado por un alfabeto, un conjunto de estados y un conjunto de… …   Wikipedia Español

  • Autómata con pila — Saltar a navegación, búsqueda Un autómata con pila o autómata de pila o autómata a pila o autómata apilador es un modelo matemático de un sistema que recibe una cadena constituida por símbolos de un alfabeto y determina si esa cadena pertenece al …   Wikipedia Español

  • Autómata probabilístico — Saltar a navegación, búsqueda Un autómata probabilístico es una generalización del automáta finito no determinista; incluye la probabilidad de una transición dada de una función de transición, convirtiéndola en una matriz de transición. Contenido …   Wikipedia Español

  • Gramática (autómata) — Una gramática ( G ) desde el punto de vista de la teoría de autómatas es un conjunto finito de reglas que describen toda la secuencia de símbolos pertenecientes a un lenguaje específico L. Dos gramáticas que describan el mismo lenguaje se llaman… …   Wikipedia Español

  • Transductor de estados finitos determinista p-subsecuencial adelantado — Los transductores de estados finitos son Autómatas de estados finitos deterministas con transiciones sobre parejas de símbolos. Un transductor de estados finitos determinista p subsecuencial adelantado (TpSSDA o EDpSST de sus siglas en inglés… …   Wikipedia Español

  • Teoría de autómatas — La teoría de autómatas es una rama de las ciencias de la computación que estudia las máquinas abstractas y los problemas que éstas son capaces de resolver. La teoría de autómatas está estrechamente relacionada con la teoría del lenguaje formal ya …   Wikipedia Español

  • Lenguaje regular — Un lenguaje regular es un tipo de lenguaje formal que satisface las siguientes propiedades: Los lenguajes más sencillos que se considerarán son los lenguajes regulares, es decir, los que se pueden generar a partir de los lenguajes básicos, con la …   Wikipedia Español

  • Construcción de subconjuntos — En teoría de la computación, la Construcción de subconjuntos es un método estándar para, partiendo de un NFA (Autómata Finito No Determinista), obtener un DFA (Autómata Finito Determinista) equivalente, es decir, que reconozca el mismo Lenguaje… …   Wikipedia Español

  • Construcción de conjunto potencia — En la teoría de la computación, la construcción de conjunto potencia es un método estándar para convertir un autómata finito no determinista (AFND) a un autómata finito determinista (AFD) que reconoce el mismo lenguaje formal. En la teoría es… …   Wikipedia Español

  • Trie — Un trie es un caso especial de autómata finito determinista (S, Σ, T, s, A), que sirve para almacenar un conjunto de cadenas E en el que: Σ es el alfabeto sobre el que están definidas las cadenas; S, el conjunto de estados, cada uno de los cuales …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”