Trabajo Colaborativo 1
Enviado por rodo3169 • 20 de Mayo de 2012 • 1.087 Palabras (5 Páginas) • 827 Visitas
TRABAJO COLABORATIVO N 1
LENGUAJES REGULARES
DIDIER ANDRES LOSADA RAMIREZ
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
ESCUELA DE CIENCIAS BÁSICAS, TECNOLOGÍA E INGENIERÍA
LA PLATA HUILA
2012
TRABAJO COLABORATIVO N 1
LENGUAJES REGULARES
DIDIER ANDRES LOSADA RAMIREZ
COD. 10814013029
GRUPO: 301405_72
TUTOR:
JESUS EMIRO VEGA
Autómatas y Lenguajes Formales
UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA – UNAD
ESCUELA DE CIENCIAS BÁSICAS, TECNOLOGÍA E INGENIERÍA
LA PLATA HUILA
2012
OBJETIVO
OBJETIVO GENERAL
Reconocer los lenguajes regulares, autómatas finitos y su aplicación.
OBJETIVOS ESPECIFICOS
Estudiar la aplicación de los lenguajes regulares y los autómatas finitos.
Adquirir las habilidades necesarias para desarrollar autómatas y máquinas que reconozcan lenguajes o computen funciones.
Distinguir los diferentes tipos de lenguajes formales existentes.
EJERCICIOS A DESARROLLAR:
1. Defina y de un ejemplo claro de: (No se aceptan ejemplos tomados del módulo, de textos guías, o de consultas bibliográficas de la Biblioteca Virtual UNAD). Son ejemplos creados con objetividad por Uds los estudiantes.
SIMBOLO
Un dato arbitrario que tiene algún significado a o efecto en la máquina. A estos símbolos también se les llama "letras" o "átomos".[1]
Es una entidad abstracta, que no se va a definir. Normalmente los símbolos son letras (a,b,c,…z), dígitos (0,1,2…9) y otros caracteres (+,*,/,-,?...).
Un símbolo también puede estar formado por varias letras o caracteres, como las palabras reservadas de un lenguaje de programación son símbolos de dicho lenguaje. Ejemplo:
- a,b,c,#,+,-,*, then, begin, end, else, …
ALFABETO
Conjunto finito de símbolos. Un alfabeto se indica normalmente con , que es el conjunto de letras en un alfabeto.
LENGUAJE
Un conjunto de palabras, formado por símbolos en un alfabeto dado. Puede ser infinito.
Se denomina lenguaje a un conjunto de palabras de un determinado alfabeto.
También un lenguaje es un conjunto de cadenas de símbolos (palabras, oraciones, textos o frases).
Un lenguaje está compuesto por Sintaxis: (gramática), que define las secuencias de símbolos que forman cadenas válidas de un lenguaje. Y por Semántica, que es el significado de las cadenas que componen un lenguaje.
Ejemplo 1:
Sintaxis: A
Semántica: es un número natural.
Diferente sintaxis en diferentes lenguajes:
A: natural
A: es un número que pertenece al conjunto de |N={1,2,3..N}
Ejemplo 2:
Sintaxis:
if a=b then write(a, " es igual a ", b )
else write(a, " es distinto a ", b )
Semántica:
Si se cumple la condición entonces se muestra un mensaje que ambos números son iguales.
Caso contrario, se escribe los número son distintos.
EXPRESION REGULAR
Podemos simplificar la especificación de un lenguaje regular utilizando nomenclatura abreviada, llamada expresión regular, de tal manera que el lenguaje unitario {a}, se denota simplemente como a.
Las operaciones de lenguajes regulares se denotan como: a U b, en vez de {a,b}; ab, en vez de {ab}; a* en vez de {a}* y a+ en vez de {a}+. El objetivo de esto es facilitar la lectura de los lenguajes regulares.
Entonces podemos definir recursivamente lo que son las expresiones regulares:
∅y ε es un lenguaje regular.
a es una expresión regular para toda a є Σ.
Si r y s son dos expresiones regulares, entonces r U s, r * s y r* son expresiones regulares.
Ningun otra secuencia de simbolos es una expresión regular.
Ejemplo 1
La
...