Diferencia entre un Autómata Finito Determinista y un Autómata Finito No Determinista

Un autómata finito determinista (AFD)

Es un autómata finito que además es un sistema determinista; es decir, para cada estado q ∈ Q en que se encuentre el autómata, y con cualquier símbolo a ∈ Σ del alfabeto leído, existe siempre a lo más una transición posible δ(q,a).

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

• Que existan dos transiciones del tipo δ(q,a)=q₁ y δ(q,a)=q₂, siendo q₁ ≠ q₂;
• Que existan transiciones del tipo δ(q,ε), salvo que q sea un estado final, sin transiciones hacia otros estados.

Un autómata finito no determinista (AFND)

Es aquel que, a diferencia de los autómatas finitos deterministas, posee al menos un estado q ∈ Q, tal que para un símbolo a ∈ Σ del alfabeto, existe más de una transición δ(q,a) posible.

Haciendo la analogía con los AFDs, en un AFND puede darse cualquiera de estos dos casos:

• Que existan transiciones del tipo δ(q,a)=q₁ y δ(q,a)=q₂, siendo q₁ ≠ q₂;
• Que existan transiciones del tipo δ(q,ε), siendo q un estado no-final, o bien un estado final pero con transiciones hacia otros estados.

Cuando se cumple el segundo caso, se dice que el autómata es un autómata finito no determinista con transiciones vacías o transiciones ε (abreviado AFND-ε). Estas transiciones permiten al autómata cambiar de estado sin procesar ningún símbolo de entrada.

Formalmente, se distingue de la 5-tupla que define a un autómata finito determinista en su función de transición. Mientras en un AFD esta función se define de la siguiente manera:

en un AFND se define como:

Para el caso de los AFND-ε, se suele expresar la función de transición de la forma:

donde P(Q) es el conjunto potencia de Q.

Esto significa que los autómatas finitos deterministas son un caso particular de los no deterministas, puesto que Q pertenece al conjunto P(Q).

La interpretación que se suele hacer en el cómputo de un AFND es que el automáta puede estar en varios estados a la vez, generándose una ramificación de las configuraciones existentes en un momento dado. Otra interpretación puede ser imaginar que la máquina "adivina" a qué estado debe ir, eligiendo una transición entre varias posibles.

Note finalmente que en un autómata finito no determinista podemos aceptar la existencia de más de un nodo inicial, relajando aún más la definición original.

Elementos que conforman un Automata Finitos

Los autómatas finitos se pueden representar mediante grafos particulares, también llamados diagramas de estados finitos, de la siguiente manera:

• Los estados se representan como vértices, etiquetados con su nombre en el interior.
• Una transición desde un estado a otro, dependiente de un símbolo del alfabeto, se representa mediante una arista dirigida que une a estos vértices, y que está etiquetada con dicho símbolo.
• El estado inicial se caracteriza por tener una arista que llega a él, proveniente de ningún otro vértice.
• El o los estados finales se representan mediante vértices que están encerrados a su vez por otra circunferencia.

Recurrencia

Recurrencia, Recursión (incorrecto en castellano) o recursividad es la forma en la cual se especifica un proceso basado en su propia definición. Siendo un poco más precisos, y para evitar el aparente círculo sin fin en esta definición:

Un problema que pueda ser definido en función de su tamaño, sea este N, pueda ser dividido en instancias más pequeñas (< N) del mismo problema y se conozca la solución explícita a las instancias más simples, lo que se conoce como casos base, se puede aplicar inducción sobre las llamadas más pequeñas y suponer que estas quedan resueltas.

Para que se entienda mejor a continuación se exponen algunos ejemplos:

• Factorial(x: Entero): Sea N := x el tamaño del problema, podemos definir el problema de forma recurrente como x*Factorial(x - 1); como el tamaño de Factorial(x - 1) es menor que N podemos aplicar inducción por lo que disponemos del resultado. El caso base es el Factorial(0) que es 1.

• Ordenación por fusión(v: vector): Sea N := tamaño(v), podemos separar el vector en dos mitades. Estas dos mitades tienen tamaño N/2 por lo que por inducción podemos aplicar la ordenación en estos dos subproblemas. Una vez tenemos ambas mitades ordenadas simplemente debemos fusionarlas. El caso base es ordenar un vector de 0 elementos, que está trivialmente ordenado y no hay que hacer nada.

Ambigüedad

Def. Posibilidad de que algo pueda entenderse de varios modos o de que admita distintas interpretaciones.

La ambigüedad pragmática se da cuando una palabra, sintagma u oración es susceptible de dos o más significados o interpretaciones.

La palabra, sintagma u oración se puede entender de más de una manera.

Ambigüedad léxica

Ambigüedad en forma de morfema o palabra. Se da cuando en un diccionario o léxico, se permite más de una interpretación para una sola palabra. Ofrece problemas de comprensión al receptor, la única solución es recurrir al contexto o a la situación. Se da cuando una misma palabra admite dos o más significados distintos.

Ambigüedad estructural

Se da en una oración o frase cuando tiene dos o más significados debido a la estructura, ya sea por el agrupamiento o la distinta función gramatical.

Ambigüedad estructural

Se da en una oración o frase cuando tiene dos o más significados debido a la estructura, ya sea por el agrupamiento o la distinta función gramatical.

Ambigüedad de agrupamiento

Oración que tiene dos estructuras posibles:

María guardó las revistas que Paco dejó bajo la cama, puede significar que las revistas han sido guardadas debajo de la cama o que las revistas que Paco había dejado bajo de la cama se han guardado en otro sitio diferente. Aunque para la primera la oración sería también: María guardó las revistas, que Paco dejó, bajo la cama.

Vio un hombre en un barco con un catalejo, que puede significar que el hombre del barco tenía un catalejo o en cambio, que el hombre ha sido visto a través de un catalejo.
Se venden zapatos de piel de señora, que puede significar que los zapatos son para señoras o que están hechos con piel de señora.

Ambigüedad funcional

Se da cuando una palabra o frase completa dos o más relaciones gramaticales, los morfemas y grupos son iguales para ambos significados.
Pasaré solo este verano aquí, La persona que dice la frase no estará acompañada durante el verano o solamente estará en ese lugar un verano.
Compraré solo este regalo, La persona que dice la frase no estará acompañada mientras compra el regalo o solamente comprará un único regalo.