Autómatas Finitos y Máquinas Secuenciales

1. Clasifica las máquinas según sus características operativas o sus recursos disponibles:

Máquinas Traductoras y Máquinas Reconocedoras Se denominan Máquinas Traductoras a aquellas que establecen una relación entre las cadenas de entrada y las cadenas de salida. Máquinas Reconocedoras su misión es validar o aceptar ciertas cadenas de entrada, arribando a estados finales definidos como “de aceptación”, sin producir ninguna cadena de salida.

Autómatas Finitos y Máquinas Secuenciales

Los Autómatas Finitos comienzan en un “estado inicial” y llegan a un “estado final” que ha sido oportunamente identificado. Las Máquinas Secuenciales no tienen previsto estados finales y en algunos casos tampoco tienen definidos estados de inicio de su operación, operan en forma ininterrumpida, sin reconocer condiciones específicas para iniciar y terminar su actividad.

Autómatas Deterministas y No Deterministas

Autómatas no deterministas: contemplan un único próximo estado a partir de cada estado posible y cada símbolo del alfabeto de entrada (la conducta autómata está completamente determinada).

Autómatas no deterministas: la función de transición puede prever más de un próximo estado para cierta condición de estado y entrada. También pueden realizar transiciones sin necesidad de leer ningún símbolo de entrada.

Diferencia entre automatismo y autonomía: los autómatas tiene comportamientos automáticos, han sido establecidos con anticipación al momento de su diseño y creación, y su modificación esta fuera del alcance del propio autómata. Por el contrario autonomía implica la capacidad de alterar por si el propio comportamiento y esto surge de la interacción del sistema con su entorno.

1. Jerarquía de Chomsky.

Chomsky propuso la jerarquía de gramáticas y utilizó las formas que toman las reglas de producción para proponer una clasificación en cuatro tipos:

Tipo 0: Lenguajes estructurados por fases o recursivamente enumerables. 🡪 Máquina de Turing

Tipo 1: Lenguajes dependientes del contexto 🡪 Autómatas linealmente acotados.

Tipo 2: Lenguajes independientes del contexto 🡪 Autómatas a Pila

Tipo 3: Lenguajes regulares o lineales. 🡪 Autómatas Finitos

[pic 1][pic 2]

[pic 3]

1. Definir alfabeto y sus características.

ALFABETO: Se denomina alfabeto a cualquier conjunto finito y no vacío de símbolos. Se usarán en adelante, letras griegas mayúsculas  [pic 4]…, con o sin subíndices, para denotarlos.

[pic 5]

Características:

• Los símbolos de un alfabeto suelen llamarse también letras o caracteres del alfabeto.
• Dos alfabetos son iguales si y sólo sí tienen exactamente los mismos símbolos, sin considerar el orden de presentación de los mismos o las repeticiones que pudieran mostrarse.
• Si todos los símbolos de un alfabeto  están también en otro alfabeto  , se dice que el primero está incluido en el segundo y se lo denota [pic 8] (inclusión amplia; también se dice que   es subconjunto de ). Si además, el segundo alfabeto posee al menos un símbolo que el primero no tiene, se dice que el primero está estrictamente incluido en el segundo, denotando en este caso [pic 11](inclusión estricta; expresándose en este caso que  es un subconjunto propio de ).[pic 6][pic 7][pic 9][pic 10][pic 12][pic 13]
• El cardinal de un alfabeto  es la cantidad de símbolos que posee y siempre será, por definición, un número entero positivo[pic 14]

Operaciones con alfabetos

• Los alfabetos pueden unirse [pic 15] = {todos los símbolos comunes y no comunes de ambos alfabetos}, intersecarse [pic 16] = {todos los símbolos comunes a ambos alfabetos}, restarse [pic 17] = {todos los símbolos del primer alfabeto que no estén en el segundo} (también se dice que este conjunto es el complemento relativo del segundo respecto del primero) y complementarse [pic 18] (en este caso deberemos definir el universal contra el cual complementar).
• Dados dos alfabetos Σ y Γ, la concatenación de Σ y Γ, denotada Σ ° Γ o sencillamente Σ Γ, es el conjunto de palabras formadas por la concatenación de cada símbolo de Σ con cada uno de Γ , en ese orden.

• Llamaremos universo de discurso de un alfabeto Σ al conjunto de todas las palabras que puedan formarse con sus símbolos, sean del largo que sean. Este conjunto, también llamado lenguaje universal de Σ, suele denotarse W(Σ) o con mayor frecuencia Σ * (que leeremos sigma estrella o estrella de Kleene de Σ). La estrella de Kleene de un alfabeto también recibe el nombre de cierre o clausura. Si quitamos de la unión la potencia cero, esto es, sacamos la palabra vacía del conjunto Σ*, obtenemos el cierre positivo.

[pic 19]

• Dos  alfabetos  son  iguales  si  y  sólo  sí  tienen  exactamente  los  mismos  símbolos,  sin  considerar  el  orden  de   resentación  de  los  mismos  o  las  repeticiones  que  pudieran  mostrarse.  

• A  la  cantidad  de  símbolos  que  posee  un Alfabeto  se  los  denomina:  Cardinal  de  un  alfabeto
• La  longitud  de  una  cadena  σ  es  el  número  de  símbolos  que  forman  a  σ.  Ejemplo:  La  longitud  de  la  cadena

 Σ =  abc3628  es  7.

• La  cadena  cuya  longitud  es  Cero  se  denomina:  Cadena  Vacia  y  se  representa  por  λ

[pic 20]Es una  notación  para  la  palabra  refleja  de  α

alfabeto  de  estados Las  maquinas  abstractas  reconocen  que  el  tiempo  avanza  y  lo  hace  en  forma  discreta,  es  decir  de  intervalo  en  intervalo.  En  cada  uno  de  esos  intervalos  de  tiempo  una  máquina  se  encuentra  en  un cierto  y  único  estado.  El  conjunto  de  sus  estados  posibles  es  finito  y  agrupado  en  un  conjunto  o  “alfabeto  de  estados”.  

...