Automata, Gramatica Y Lenguajes

Índice
Introducción. 1
Autómata, gramáticas y lenguajes. 2
Lenguajes Regulares y Expresiones Regulares 2
Definición. 2
Ejemplos. 3
Autómata finito determinista afd. 4
Ejemplo. 4
Autómata finito no determinista afn. 5
Definición. 5
Ejemplo. 6
Equivalencia de afn y afd. 7
Autómatas finitos y expresiones regulares. 8
Propiedades de los lenguajes regulares. 9
Bibliografía.13

Introducción.

La teoría de autómatas, gramáticas y lenguajes son la herramienta matemática que ha permitido el desarrollo de compiladores, intérpretes, editores e impresores de código, verificadores de código y otras herramientas. La Materia de Lenguajes Formales y Autómatas introduce conceptos abstractos un tanto complicados para los estudiantes de Informática.
Es necesario comprenderestos temas para saber y conocer todos los términos matemáticos que van de la mano de la programación y la lógica.

Autómata, gramáticas y lenguajes.
Lenguajes Regulares y Expresiones Regulares
Definición.
Las expresiones regulares fueron introducidas en 1956 por kleene y son una notación alternativa a la gramática lineal o la derecha para describir lenguajes regulares, cada expresiónregular denota un lenguaje regular.
Lenguajes regulares es la aplicación los operadores unión, producto cerradura y concatenación.
Expresiones regulares forma de describir cadenas de caracteres, permite realizar búsquedas o sustitución de gran complejidad.

Operadores:

Unión: Si L y M son dos lenguajes, su unión se denota por L ∪ M
Concatenación: La concatenación es: LM o L.M
Cerradura (ocerradura de Kleene): Si L es un lenguaje su cerradura se denota por: L*.

Usamos operaciones para construir expresiones que describen lenguajes, las cuales se denominan expresiones regulares. Un ejemplo es:

(0 ∪ 1)0∗

El valor de una expresión regular es un lenguaje. En este caso el lenguaje consiste en todas las palabras que empiezan con 1 o 0 seguido por cualquier número (finito) de 0 s.Otro ejemplo de una expresión regular es

(0 ∪ 1)∗

Empieza con el lenguaje (0 ∪ 1) y se aplica la operación * . El valor de esta expresión son todas las palabras posibles de 0 s y 1s.

Si R y S son expresiones regulares sobre Ʃ, también lo son:
RS
R US
R*
RS representa la concatenación de los lenguajes representados por R y S;
RUS representa su unión, y R* representa la cerradura dellenguaje
Representado por R.
La representación de lenguajes regulares por medio de expresiones regulares no es única. Es posible que haya varias expresiones regulares diferentes para el mismo lenguaje. Por ejemplo, b(a U b)* y b(b U a)* representan el mismo lenguaje.

Ejemplos.

Encontrar expresiones regulares que representen los siguientes lenguajes, definidos sobre el alfabeto Ʃ = {a, b}.1. Lenguaje de todas las palabras que comienzan con b y terminan con a.

b (a U b)*a.

2. Lenguaje de todas las palabras que tienen exactamente dos a ’ s.

b*ab*ab*.

3. Lenguaje de todas las palabras que tienen un número par de símbolos (palabras de longitud par).

(aa U ab U ba U bb)*.

4. Lenguaje de todas las palabras que tienen un número impar de símbolos(Palabras de longitud impar).

a(aa U ab U ba U bb)* U b(aa U ab U ba U bb)*.

5. Lenguaje de todas las palabras que tienen un número par de a0s.

b*(ab*a)*b*.
(ab*a U b)*.
(b*ab*ab*)* U b*.
b*(b*ab*ab*)*b*.

Autómata finito determinista afd.

Sistema compuesto por un conjunto finito de estado, un estado, una salida y una función de transustancia, que define los cambios de estado delsistema formalmente. Una autómata finita se define como un sistema M=<Ʃ, Q, q, F, &>, en el que:
Ʃ es un alfabeto.
Q es un conjunto finito no vacio de estados.
q es un estado inicial q € Q
F es un conjunto de estados finitos
& es una funcia de transición tal que &: QXƩ →Q
Un afd se caracteriza por el hecho de que para cada estado y para cada símbolo del alfabeto, la...