Automata Y Lenguajes Formales

TRABAJO COLABORATIVO 1

AUTOMATAS Y LENGUAJES FORMALES

PRESENTADO POR:

ZAIDA PARADA GRANADOS

GRUPO: 26

TUTOR:

CARLOS ALBERTO AMAYA TARAZONA

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA “UNAD”

CEAD PAMPLONA

COLOMBIA

2012

INTRODUCCIÓN

En el presente trabajo colaborativo No. 2, reconoceremos los lenguajes independientes de contexto, que también se conocen con el nombre de gramáticas de contexto libre, los cuales son un método recursivo sencillo de especificaciones de reglas gramaticales con las que se pueden generar cadenas de un lenguaje. Es factible producir de esta manera todos los lenguajes regulares, además de que existen ejemplos sencillos de gramáticas de contexto libre que generan contextos no regulares. Las reglas gramaticales de este tipo permiten que la sintaxis tenga variedad y refinamientos mayores que los realizados con lenguajes regulares, en gran medida sirven para especificar la sintaxis de lenguajes de alto nivel y otros lenguajes formales, decimos que los conoceremos en forma práctica porque simularemos un proceso, mediante el programa recomendado por el tutor, pudiendo clasificar desde los lenguajes más sencillos, como son los regulares que se pueden generar a partir de lenguajes de un elemento con la aplicación de ciertas operaciones estándar realizadas un número finito de veces, realizando así una profundización y transferencia socializándola con nuestro grupo colaborativo, vamos aprovechar y a valorar estas herramientas las cuales se reflejaran en nuestro crecimiento personal, poniéndolas en práctica en nuestro entorno laboral, concientizándome de que cada día la Tecnología nos exige más y por ello debemos crear una disciplina y responsabilidad en cada uno de los temas que en este caso nos ofrece este curso por medio de la unidad 2, de autómatas y lenguajes formales y el cual es base para la Ingeniería de Sistemas y para la proyección en soluciones de problemas. A través del recorrido por cada uno de los capítulos de la unidad dos nos iremos capacitando, para llevar los conocimientos de una forma teórica a una práctica, analizando, investigando y comprendiendo cada uno de los conceptos para al final tener un conocimiento amplio de los temas tratados en esta unidad, en los que respecta a lenguajes independientes del contexto.

OBJETIVO GENERAL:

Conocer los modelos de computación que corresponden a los lenguajes independientes del contexto y su aplicación.

OBJETIVOS ESPECÍFICOS

• Generalizar los conceptos de autómatas finitas y gramáticas regulares.

• Reconocer el potencial de procesamiento del lenguaje del autómata con los Autómatas de pila.

DESARROLLO DE LA ACTIVIDAD

1. Calcular el autómata mínimo correspondiente al siguiente autómata finito determinista.

1. Identifique los componentes del autómata (que tipo de tupla es):

El autómata está definido por la siguiente quíntupla

:A = (Q, Σ, f, q, F) donde:

• Q es un conjunto de estados.

• Σ es el alfabeto de entrada

• δ: Q X Σ → Q es la función (total) de transición.

• q0 ∈ Q es el estado inicial.

• F⊆ Q es el conjunto de estados finales.

A = ({q0, q1, q2, q3, q4, q5, q6, q7} , {0,1} , δ , qo, { qo,q2, q3, q4, })

f está definida de la siguiente manera:

δ(q0, 0) = q1

δ(q0, 1) = q6

δ(q1, 0) = q2

δ(q1, 1) = q3

δ(q2, 0) = q1

δ(q2, 1) = q5

δ(q3, 0) = q1

δ(q3, 1) = q4

δ(q4, 0) = q7

δ(q4, 1) = q4

δ(q5, 0) = q7

δ(q5, 1) = q3

δ(q6, 0) = q7

δ(q6, 1) = q3

δ(q7, 0) = q7

δ(q7, 1) = q3

2. Identifique la tabla de transición

Tabla de transiciones

f 0 1

→#q0 q1 q6

q1 q2 q3

...