26m ll,,ll;




























LENGUAJES Y AUTOMATAS I

SCD-1015









Índice

INTRODUCCIÓN 1

PRÁCTICA 1
CUADRO COMPARATIVO DE LOS TRADUCTORES Y CLASIFICACIÓN DE LENGUAJES 2
PRÁCTICA 2
OBTENER UN ALFABETO A PARTIR DE UN LENGUAJE Y VICEVERSA 4
PRÁCTICA 3
OBTENER UN PROGRAMA QUE IMPLEMENTE UNA EXPRESIÓN REGULAR 6
PRÁCTICA 4
OBTENER UN PROGRAMA QUEIMPLEMENTE LENGUAJES SIMPLES REPRESENTADOS
CON AFD´s 8
PRÁCTICA 5
OBTENER A TRAVES DE UN LENGUAJE DE ALTO NIVEL, LA REPRESENTACION DE UNA MAQUINA DE TURING. 10
PRÁCTICA 6
ESTRUCTURA DE UN ANALIZADOR LÉXICO (utilizar un generador de analizador
Léxico o un LP) 12
PRÁCTICA 7
ESTRUCTURA DE UN ANALIZADOR SINTACTICO (utilizar un generador de analizador
sintáctico o un LP) 14



LISTA DEMATERIAL, EQUIPO O REACTIVO A UTILIZAR 16
LISTA DE BIBLIOGRAFÍA REQUERIDA 17
CONTROL DE CAMBIOS DEL MANUAL DE PRÁCTICAS 18
INTRODUCCIÓN

Desde su nacimiento, la teoría de autómatas ha encontrado aplicación en muy diversos campos.

Esto se debe a que resulta muy natural considerar, tanto los autómatas como las máquinas secuenciales, sistemas capaces de transmitir (procesar) Información.En definitiva, esto es equiparable a cualquier sistema existente en la naturaleza, que recibe señales de su entorno, reacciona ante ellas y emite así nuevas señales al ambiente que le rodea.

Algunos De los campos donde ha encontrado aplicación la teoría de autómatas son:

Teoría de la Comunicación
Teoría de Control
Lógica de los circuitos secuenciales
Ordenadores
Teoría lógica de lossistemas evolutivos y auto
Reproductivos
Reconocimiento de patrones
Fisiología del sistema nervioso
Traducción automática de lenguajes

Lenguajes y autómatas:
Un autómata resuelve un problema mediante el cálculo de una función de una forma autónoma: Recibe unos datos y, cuando termina su trabajo, da un resultado. El mismo problema puede recibir otra colección de datos distinta(‘instance’-ejemplar) yda un resultado correcto en cada caso mediante el cálculo de la misma función.
Un ejemplar se puede ver como una palabra de un lenguaje. El conjunto de ejemplares de entrada para los que el problema tiene solución es un lenguaje. El problema tiene solución cuando existe un autómata que calcula el resultado correctamente. Hay lenguajes que no requieren autómatas tan complejos como las lasmáquinas de Turing para resolver los problemas que se plantean sobre ellos. Más simples son los autómatas finitos y los autómatas con pila. Cada tipo de autómatas reconoce una clase de lenguajes.

Datos Autómata Resultado
Los algoritmos de generación de lenguajes se llaman gramáticas. Estos mecanismos fueron propuestos por Chomsky para definir estructuras sintácticas en el estudiodel lenguaje natural (1950). Las partes del lenguaje natural libres de contexto tienen una estructura definida por gramáticas incontextuales y los lenguajes incontextuales son reconocidos por autómatas con pila. La Informática aprovechó rápidamente estos estudios sobre el lenguaje natural aplicándolos a la construcción de analizadores sintácticos, imprescindibles en compilación.
Hay una jerarquíade lenguajes formales, a la que corresponde una jerarquía de autómatas:
Lenguajes regulares  Lenguajes incontextuales  Lenguajes contextuales
Autómatas finitos  Autómatas con pila  Máquinas de Turing.
Todo ello se corresponde con el nivel de abstracción requerido para resolver los tipos de problemas asociados a un determinado lenguaje con las herramientas más sencillasposible, en aras de la eficiencia.


Práctica
1


FUNCION DE LOS TRADUCTORES Y CLASIFICACIÓN DE LENGUAJES

Observaciones: Esta práctica cubre la Práctica # 1 del temario que dice “Realizar un cuadro comparativo de los traductores que incluya ventajas, desventajas y características”, la Práctica #2 del temario que dice “Clasificar una lista de lenguajes, ambientes de desarrollo y...