Autómatas-trabcolab1

AUTÓMATAS FINITOS
LENGUAJES REGULARES

Presentado por:
LUIS MIGUEL GARRIDO AMAYA – 1100623566
CEAD COROZAL – miguegarrido@hotmail.com

Tutor:
Ing. JAIRO ARMANDO RIAÑO HERRERA
CEAD SOGAMOSO – jairo.armando@gmail.com

Curso Académico:
AUTÓMATAS Y LENGUAJES FORMALES

Grupo Colaborativo:
301405_45

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIA “UNAD”
ESCUELA DE CIENCIAS BÁSICAS,TECNOLOGÍAS E INGENIERÍAS
INGENIERÍA DE SISTEMAS
2009
TABLA DE CONTENIDO

Página

Introducción…………………………………………………………………………… 3

Objetivos………………………………………………………………………………. 4

AUTÓMATAS FINITOS...……………………………………………………………. 5

MINIMIZACIÓN DE AUTÓMATAS FINITOS……………………………………… 10

AUTOEVALUACIÓN……………………………………………………………….… 18

Conclusión………………….…………………………………………………………. 20BIBLIOGRAFÍA……………………………………………………………………….. 21

WEBGRAFÍA………………………………………………………………………….. 22

INTRODUCCIÓN

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 validarinformación y entre ellos, se encuentran los Autómatas Finitos y los Lenguajes Regulares que contienen las expresiones regulares, que tienen parecido a una especie de lenguaje que se puede usar para buscar, remplazar y sobreponer ciertos patrones en un texto.

OBJETIVOS

OBJETIVO GENERAL

✓ Reconocer los lenguajes regulares, autómatas finitos y su aplicación.

OBJETIVOS ESPECIFICOS

✓Analizar las expresiones regulares como método de descripción de lenguajes regulares.

✓ 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 y su clasificación en ordencreciente de complejidad, así como los autómatas reconocedores y las gramáticas generadoras.

AUTÓMATAS FINITOS
LENGUAJES REGULARES

1.- Obtener el lenguaje reconocido por el siguiente AFD:

A = ({a, b, c}, {q0, q1, q2, q3, q4}, f, q0, {q2})

f(q0, a) = q1 f(q0, b) = q4 f(q0, c) = q4
f(q1, a) = q4 f(q1, b) = q1 f(q1, c) = q2
f(q2, a) = q4 f(q2, b) = q4 f(q2, c) = q2
f(q3, a) = q4 f(q3,b) = q3 f(q3, c) = q2
f(q4, a) = q4 f(q4, b) = q4 f(q4, c) = q4

Tabla de Transiciones
|f |a |b |c |
|q0 |q1 |q4 |q4 |
|q1 |q4 |q1 |q2 |
|# q2 |q4 |q4 |q2 |
|q3 |q4 |q3 |q2 |
|q4 |q4 |q4 |q4|

Diagrama de Transición
[pic]

El lenguaje reconocido es A= {ac}

2.- Determinar el lenguaje que reconoce el siguiente AFD:
[pic]
El lenguaje que reconoce es:

La función δ: {q1, q2, q3}*{1, 2, 3} {q1, q2, q3} viene dada por:

δ (q1,1)=q1 δ (q1,2)=q1 δ (q1,3)=q2

δ (q2,1)=q3 δ (q2,2)=q3 δ (q2,3)=q3

δ (q3,1)=q3 δ (q3,2)=q3 δ (q3,3)=q3

Tabla de Transición|δ |1 |2 |3 |
|q1 |q1 |q1 |q2 |
| # q2 |q3 |q3 |q3 |
|q3 |q3 |q3 |q3 |

3.-Dado el autómata finito siguiente:
[pic]
Definir la gramática lineal izquierda quedescribe el mismo lenguaje reconocido por el autómata.

Tabla de Transición
|f |0 |1 |
|A |B |C |
| B |B |B |
|C |C |D |
|D |E |E |
|# E |E |E...