TRABAJO No.1 DE AUTOMATAS Y LENGUAJES FORMALES

TRABAJO DE AUTOMATAS Y LENGUAJES FORMALES

N°1

JAIRO ANTONIO CASTRO CASAS

CC: 11203416

GUSTAVO LUIS MORELO ESPITIA

CC: 11039948

NESNEL REYES IDROBO

CC: 10693354

HERNANDO ORTIZ SANABRIA

CC: 11431332

GRUPO: 301405_9

CARLOS ALBERTO AMAYA TARAZONA

UNIVERSIDAD NACIONAL ABIERTA Y ADISTANCIA

UNAD

OCT/25/12

TABLA DE CONTENIDO

1. INTRODUCCIÓN................................................................................................... 1

2. OBJETIVOS........................................................................................................... 1

3. DESARROLLO DE ACTIVIDADES PROPUESTAS.............................................. 21

4. CONCLUSIONES................................................................................................ 1

5. BIBLIOGRAFIA Y CIBERGRAFIA....................................................................... 1

INTRODUCCION

Los lenguajes regulares son la buena manera de validar campos del texto tales como nombres, las direcciones, los números de teléfono, y otra información del usuario. Podemos utilizarlas para obligar la entrada, aplicar reglas del formato, y mucho más; hay varios métodos de cómo validar información.

Los lenguajes regulares nos dotan de los fundamentos o las bases para describir o buscar coincidencias de acuerdo de unas reglas de sintaxis predefinidas. Una expresión regular es un patrón de caracteres que comparamos con una determinada cadena o parcela de texto. La estructura de una expresión regular es similar a una típica expresión aritmética: varios elementos son combinados para conseguir una expresión más compleja. El potencial de las expresiones regulares se basa en esto, en poder realizar múltiples combinaciones de los distintos elementos que la pueden conformar.

A veces necesitamos encontrar algo concreto en un texto o cadena, o reemplazar algo por otra cosa; ya sea en una aplicación, o en un lenguaje de programación. Por ejemplo si queremos buscar "tag" y reemplazarlo por "etiqueta" la mayoría de aplicaciones o lenguajes tienen una función para hacerlo de forma sencilla.

Pero a veces lo que queremos hacer es más complejo, porque puede que en vez de ser una palabra o parte de palabra simple, necesitemos hacer algo como "búscame todas las palabras que acaben en 'f' y que empiecen por un número del 2 al 71" (por ejemplo) o "reemplaza las palabras que contengan este grupo de letras por esto".

En estos casos podemos utilizar los lenguajes regulares (que se pueden llamar regex o regexp de forma abreviada), que es como un lenguaje para poder definir exactamente qué es lo que queremos buscar o reemplazar.

Las expresiones regulares es como una especie de lenguaje que se puede usar para buscar y/o remplazar ciertos patrones en un texto.

OBJETIVOS

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.

Adquirir el conocimiento y competencia para poder recrear autómatas sencillos en un simulador. De igual forma verificar el lenguaje que reconoce.

DESARROLLO DE LA ACTIVIDAD

Para el siguiente ejercicio, recordaremos ciertas apreciaciones, conceptos o afirmaciones acerca de las Expresiones Regulares, comúnmente denotadas como “ER”:

Una expresión regular es una forma de representar cierto tipo de lenguajes sobre un determinado alfabeto. Son exactamente los aceptados por los autómatas de estado finito.

Si tomamos como A un alfabeto, unas posibles expresiones regulares sobre ese alfabeto podrían ser: (identifique que lenguaje reconoce esa ER)….

Ø es una ER que denota el Lenguaje?

R//= L{Ø}=Ø

λ es una ER que denota el lenguaje?

R//= L{λ}=λ

En general los lenguajes que pueden representarse mediante una expresión regular se llaman lenguajes regulares. Estos coinciden con los aceptados por los autómatas finitos.

Es importante que tengamos definido o claro que Si r y s son ER denotando los lenguajes R y S, entonces se definen tres operaciones muy básicas:

- Unión: (r + s) es una expresión regular ER que denota el lenguaje R U S

- Concatenación: (r.s) algunos autores lo toman como (r.s) es una expresión regular ER que denota le lenguaje RS.

- Clausura: r* es una expresión regular ER que denota el lenguaje R

Para efectos de plasmar las ER, los paréntesis se pueden eliminar siempre y cuando los símbolos y caracteres no alteren la interpretación de otros caracteres o cadenas. La precedencia de las operaciones es: clausura / Concatenación / Unión.

Para los siguientes ejercicios identifique el lenguaje que reconoce y plasme cinco posibles cadenas válidas que representan esa ER:

Si A = {a,b,c}

(a + b)

EXPRESION CADENAS POSIBLES

(a + b) ab

aabb

ababab

aaabb

abbbbbbb

(a + b)*

EXPRESION CADENAS POSIBLES

(a + b)* {λ}

aaabbb

aaaaabb

abaabbaabb

aabbabab

(a + λ )b*

EXPRESION CADENAS POSIBLES

(a + λ )b* a

...