Conceptos

Conceptos

1. Cadenas

   • Una cadena o palabra sobre un alfabeto Σ es cualquier sucesi´on finita de ele- mentos de Σ. Admitimos la existencia de una ´unica cadena que no tiene s´ımbolos, la cual se denomina cadena vac´ıa y se denota con λ.

2. Automata

   • Es una especie de computadora abstracta, que dada una entrada produce una salida, es decir calcula una función

3. Autómata finito deterministico

   • La transición desde un estado puede tener como destino un único estado. Por eso se llama determinista.
     • No se aceptan transiciones con cadenas vacías.
       • Una cadena es aceptada si su transición es hacia un estado final.

4. Máquina de estado finito

   • es un modelo computacional 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 finito, una función de transición, un estado inicial y un conjunto de estados finales

5. Alfabeto

   • Conjunto finito y no vacío cuyos elementos se denominan símbolos, es decir es una secuencia de símbolos

6. Autómata finito no deterministico

   • Permite transiciones con cadenas vacías
     • No siempre se permite el uso de backtracking
       • La transición desde un estado puede tener multiples destinos

7. Santamaria Bernal Álvaro Daniel

Bilder und Dateien der Mindmap