Autómatas y lenguajes formales

Autómatas y lenguajes formales

Teoría

1. ¿Qué es un problema insoluble?

Los problemas insolubles, son aquellos problemas los cuales, en principio, se pueden resolver, sin embargo en el momento de llevarlos a la práctica, consumen demasiado tiempo, tanto así que las computadoras se vuelven inútiles para la solución del problema, con excepción en los casos simples. Son problemas que no son eficientes para la solución en computadora

1. ¿Qué es un estado y cuál es su propósito?

Un estado es aquel espacio que funciona para recordar el historial relevante del sistema, donde cada uno tiene guardado información que entra de un estado anterior a él, es un conjunto particular de instrucciones, donde dentro de cada estado encontramos una información que será procesada y transferida a otros estados para lograr completar una información general, serán ejecutada en respuesta a la entrada de la máquina.

Existe, estado normal, estado inicial, y estado final o de aceptación.

1. ¿Qué entiende usted que sería un autómata finito?

Un autómata finito, maquina de estado finito o también llamado AF, realiza operaciones, cómputos de una forma automática sobre una entrada para poder producir una salida. El modelo de AF, es aquel que esta conformado por un alfabeto, y un conjunto de estados finito, dentro de estos estados, está la función de transacción, el cual recibe la información del estado inicial, el cual es el que recibe la cadena de caracteres que pertenecen al alfabeto, esto es la entrada, que va pasando de un estado a otro, completando información para así, acabar en un estado final o estado de aceptación y determinar una información completa, que es la salida.

Este autómata acepta un lenguaje llamado alfabeto, solo funciona si dentro de este autómata, la información tiene la salida en el estado final o de aceptación  

Práctica 

1. A partir del siguiente autómata, defina cuales de las siguientes 4 palabras pueden ser asimiladas.

[pic 1]

1. (10%) Determine si los siguientes autómatas son AFD O AFND .

a.  AFD

[pic 2]  

b. AFND

[pic 3]

c. AFND[pic 4]

d. AFND[pic 5]

1.  A partir del siguiente autómata

[pic 6]

1. Determine si el autómata es AFD o AFND

R// AFD

1. En un conjunto llamado Q, defina cuales son los estados que reconoce el autómata Q={ q0, q1, q2 }

1. En un conjunto llamado F, defina cual o cuales son los estados finales del autómata F ={ q2}

D. Defina cuál es el vocabulario del autómata

Σ={ a, b}

E. Complete el conjunto de estados resultantes a partir de las siguientes funciones de transición

δ(q0,a)={ q1 }

δ(q0,b)={ q2 }

δ(q1,a)={ q1 }

δ(q1,b)={ q2}

1. Dado el siguiente Autómata

[pic 7]

1. Determine si el autómata es AFD o AFND

R// AFD

1. En un conjunto llamado Q, defina cuales son los estados que contiene el autómata Q={ q0, q1, q2 }
2. En un conjunto llamado F, defina cual o cuales son los estados finales del autómata F ={ q1 }
3. Defina cual es el vocabulario del autómata

Σ={ 0, 1}

1. Complete las siguientes funciones de transición

δ(q0,0)={ q0 }

δ(q0,1)={ q1 }

δ(q1,1)={ q1 }

δ(q1,0)={ q2 }

δ(q2,1)={ q1 }

δ(q2,0)={ q1 }

1. Determine 3 palabras asimiladas por el autómata

W1:  101

W2:  0100

W3: 0011001

1. Dado el siguiente autómata defina:

[pic 8]

1. Determine si el autómata es AFD o AFND

R// AFD

B. En un conjunto llamado Q, defina cuales son los estados que contiene el autómata Q={ A,B,C}

En un conjunto llamado F, defina cual o cuales son los estados finales del autómata F ={ B }

D. Defina cual es el vocabulario del autómata

Σ={ 0, 1}

E. Complete las siguientes funciones de transición

δ(A,0)={ B }

δ(B,0)= { B }

δ(B,1)= { B }

...