Trabajo Colaborativo 1

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

...