UNAD - AUTOMATAS PRIMER MOMENTO

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA UNAD

AUTOMATAS Y LENGUAJES FORMALES

ACTIVIDAD EVALUACIÓN INICIAL

Preparado por

Cesar Andrey López Cajamarca

Johan Gustavo Hernández Moreno

Dennix Alberto Barrios Castillo

Curso 301405_33

La Dorada, Colombia

2015

Desarrollo de actividades

Problemas a desarrollar:

Plasme la tabla de transición. Identifique que tipo de autómata es (AFD o AFND) y justifique su respuesta. (No se trata de dar el concepto de determinismo)

Es un autómata no determinista ya que según el diagrama hay estados que tienen dos transacciones (q1 a q3 o q2 a q4), no me determina una ruta específica. El determinista es más directo solo tiene una transacción.

Identifique los elementos (Tupla que es) (Asociadas con los elementos del autómata del ejercicio propuesto). Debe explicar y describir cada elemento y la función y significado en el autómata. Conceptos y definiciones adicionales.

Tupla del ejercicio

Descripción:

Ʃ={a,b,c}; letras del alfabeto de entrada

K= {q0, q1, q2, q3, q4, }; Es el conjunto de estados

δ: {q0, q1, q2, q3, q4 } × {a,b,c} → {q0, q1, q2, q3, q4 } → q0 → { q3 , q4, } ; Función total de transición de estados

q0 € K; Estado inicial

F; es un conjunto de estados finales o aceptables

Lenguajes alfabetos y expresiones regulares:

Símbolo: Representación distinguible de cualquier información, pueden se: x,6,#, etc; es una entidad visible.

Alfabeto: conjunto finito y no vacío de símbolos, por ejemplo Ʃ={x,y}; con ellos podemos formar las cadenas o palabras.

Lenguaje: Conjunto de palabras, cuando hablamos sobre el alfabeto Ʃ a cualquier subconjunto de Ʃ*, un lenguaje es una clase especial de conjunto que podemos especificar como finito.

Expresión regular: El objetivo de las expresiones regulares es representar todos los posibles lenguajes definidos sobre un alfabeto Σ, en base a una serie de lenguajes primitivos, y unos operadores de composición. Pueden ser de tipo Alfa o de tipo beta.

Orden de prioridad de los operadores: s de menor a mayor: * . +, pueden alterarse con paréntesis de forma análoga a las expresiones matemáticas.

Tomado de Unidad 1: Lenguajes Regulares, Descripción de Lenguaje, Alfabeto y ER de http://campus13.unad.edu.co/campus13_20151/mod/lesson/view.php?id=4734&pageid=1547

Identifique el lenguaje que genera.

Para identificar el lenguaje primero que todo debemos hallar la función de transición extendida. Este procedimiento se haría así:

Ŝ= (estado inicial, conjunto de las palabras)=estado final

W=abca

Ŝ= (Q0, W)=Q4

La función de transición extendida no trabaja con un elemento de cadena sino con varios elementos de la cadena de caracteres.

Entonces el lenguaje del autómata M seria:

L(m)={W│Ŝ(Q_0,W)∈F

Muestre en el simulador (gráficamente) como recorre una cadena válida. Explique cada secuencia. (No se trata solo de captura las imágenes, estas deben ser explicarlas en pie de página o de lo contrario no tienen validez)

Trabajaremos en JFLAP la cadena valida: abca

En las anteriores imágenes vemos gracias al programa JFLAP en las opciones de Imput seleccionamos step by state podemos seleccionar la cadena abca y la corremos.

Al dar la opción step veremos la secuencia una a una de la cadena; en las imágenes vemos como pasa del estado inicial q0 al estado q1 por el alfabeto a, vemos en el recuadro inferior izquierdo nuestra cadena de color azul la cual indica que está en el estado aceptado; del mismo modo vemos que pasa del estado q0 al estado q2 ya que el símbolo de vacío no altera solo abre el paso a nuestra cadena, de igual forma se muestra

...