trabajo colaborativo 1 lenguajes y automatas formales

TRABAJO COLABORATIVO 1











PRESENTADO POR









TUTOR
CARLOS ALBERTO AMAYA TARAZONA
















UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD
ESCUELA DE CIENCIAS BASICAS E INGENIERIAS ECBTI
301405_31 AUTOMATAS Y LENGUAJES FORMALES
BOGOTA D.C
2013



1. Explicar las expresiones regulares

si A = {a,b,c}



Representa ellenguaje de las cadenas que pueden o no empezar por la expresión que significa 1 o más elementos de a combinado con uno y solo un elemento de b, siendo este último obligatorio en cada iteración; y terminar obligatoriamente con la expresión regular que funciona exactamente igual a la anterior.



Representa (ninguna-una o mas) cadenas compuestas por “ninguno, uno o mas” elementos de a y uno y solouno de b en cada iteración.


Representa el conjunto de las cadenas compuestas por mínimo uno o mas elementos de a, seguidos de una cadena vacía obligatoria, y finalizando opcionalmente con una o mas combinaciones de


Representa el conjunto de las cadenas que empiezan por b y terminan opcionalmente en una o más combinaciones


Representa el conjunto de la o las cadena(s) lambdaRepresenta el conjunto de las cadenas que inician por minimo uno o mas combinaciones de (que a su vez expresan la presencia de ninguno, uno o más elementos de a) seguidas


Representa el lenguaje de las cadenas que comienzan ineludiblemente por una o n repeticiones de (que significa “1” obligatorio y cero, una o n repeticiones de “0”) y terminan en .


Representa el conjunto de cadenasque comienzan en mínimo 1 o n repeticiones de (0 obligatorio y cero, una o n repeticiones de 1) y terminan en 0.





Representa el conjunto de las cadenas que inician por una o mas repeticiones de (que a su vez significan una o mas repeticiones de “1” seguidas por 10) y terminan en 0


Representa el conjunto de cadenas que inician por cero, una o mas repeticiones de ”1”, seguidas porcero, una o mas repeticiones de “0” y terminadas en la expresión 10.


Representa el conjunto de expresiones que inician con una o más repeticiones de “0” y terminan con una o más repeticiones de “1”


Representa el conjunto de las cadenas que inician con cero, una o mas repeticiones de la expresión 0+1 (una o mas repeticiones de “0” seguidas por un “1” obligatorio) seguidas por la expresiónobligatoria 11, y finalizadas con n repeticiones opcionales de (una o más repeticiones de “1” seguida por 0 obligatorio)


2. Represente el grafo
A = ({q 0 , q1 , q 2 , q 3 } , {0,1} , f , q 0 , { q 2 })









Plásmelo en el simulador

Realice la tabla de transición correspondiente.
Entradas

Estados
0
1
q0
{q0,q1}
q0
q1
q3
q2
q2
q3

q3
q3
q3

Compruebe ellenguaje aceptado



Identifique la expresión regular que permite identificar que cadenas son válidas y que acepta el autómata.
(0+1)*01
Identifique que denotación de estados está errada y corríjala.
Los estados deben representarse con la notación del problema.


3. Acorde al autómata del ejercicio N 2, Realice:

Identifique si es un AFD ó AFND y justifique por qué.

La máquinaanterior hace referencia a un autómata de estado finito no determinista, ya que, existe elección en las transiciones de ciertos estados a otros. El estado cuenta con dos caminos para al entrado 0.

Si dado el caso es un AFND conviértalo en el simulador a un AFD y plásmelo en el trabajo sus cadenas válidas. Analice si son las mismas cadenas que acepta al autómata antes de convertirlo.

El nuevoAFND debe plasmarlo en el simulador.

Compruebe el lenguaje aceptado

Identifique la expresión regular que permite identificar que cadenas son válidas y que acepta el autómata.

Analice si la ER y el Lenguaje aceptado es el mismo o no al ejercicio Número 2. Justifique sus respuestas.


Son autómatas equivalentes, por ende, tienen el mismo patrón de aceptación y reciben las mismas...