Teoria De La Computacion

IIS340 TEORÍA DE AUTOMATAS Y LENGUAJES FORMALES
APUNTES DEL CURSO


IIS340 : Teoría de Autómatas y Lenguajes Formales

Capítulo 1


IIS340 : Teoría de Autómatas y Lenguajes Formales

Capítulo 1

CAPITULO 1: INTRODUCCIÓN Y DEFINICIONES BÁSICAS
1.1. ¿QUÉ ES UN LENGUAJE FORMAL? Un Lenguaje normal o natural, como por ejemplo el lenguaje español u inglés, son la clase de lenguajes quehan evolucionado con el paso del tiempo y tienen por fin la comunicación humana. Este tipo de lenguajes están en constante evolución y sus reglas gramaticales solo pueden ser explicadas y no determinadas en cuanto a la estructura del lenguaje. En contraste, un lenguaje formal esta definido por reglas preestablecidas y se ajustan con rigor a ellas, ejemplos son los lenguajes computacionales como Co Pascal. 1.2. ¿QUÉ ES UN AUTÓMATA? Por ahora lo definiremos en forma muy general como una “Máquina conceptual o teórica para el reconocimiento de patrones”. Se utilizan o asocian en general con los aspectos prácticos del procesamiento de lenguajes y en lo particular con la construcción de compiladores. Un compilador consta básicamente de 3 componentes: analizador léxico; analizador sintáctico yel generador de código (ver Figura 1).

A lzd naaor i L c é o xi P aa r m ogr F nt ue e

A lzdor naa i S atc i c o nt i

G ea rde e r do n Ci ód go

C g ódi o Oe bt j o
Figura 1: Componentes básicos de un compilador.

000 111 101 100 011 000 111 001

El analizador léxico, recibe como entrada una cadena de símbolos (el programa fuente) y tiene por función la identificación de secuenciasmultisímbolos dentro de la cadena y que representan un solo objeto. Por ejemplo, palabras reservadas, nombres de variables, identificadores especiales como el de asignación en Pascal, etc. En definitiva, el analizador léxico recibe como entrada el programa fuente y genera como salida una cadena de componentes léxicos, cada uno de los cuales representa un solo objeto que pudo haber sidorepresentado con más de un símbolo en la cadena.

3

IIS340 : Teoría de Autómatas y Lenguajes Formales

Capítulo 1

El analizador sintáctico, recibe como entrada la cadena de componentes léxicos y analiza en el sentido de que estén correctamente dispuestos u organizados, por ejemplo que dado un componente léxico “IF” (en Pascal), existan y estén en la secuencia adecuada los componentes léxicos“THEN” y “ELSE”. Como se podrá apreciar, estos dos primeros componentes de un compilador, dependen en gran medida de la capacidad de reconocer patrones. Si estos patrones se basan en reglas gramaticales, entonces el proceso de reconocimiento también puede basarse en estas reglas. 1.3. DIAGRAMAS Y TABLAS DE TRANSICIÓN Una tarea básica para un analizador léxico es identificar los nombres de variables yverificar que estas cumplan con las reglas gramaticales del lenguaje. Por lo general, un nombre de variable siempre comienza con una letra y luego puede contener unh conjunto de letras y dígitos. Una forma clara de representar la estructura de un nombre de variable aceptable es utilizar un diagrama de transiciones o diagrama de estados. Estos diagramas son de mucha utilidad a la hora de construir untrozo de programa que reconozca la ocurrencia de nombres de variables.
Ac o ro Tan i r scón i

l ta er l ta er 1 dí t gi o 2 3 dí t gi o
E add s oe t ac t i e ac p ón

E adI i i s o n al t c

Figura 2: Diagrama que representa la sintaxis de un nombre de variable

A partir del diagrama de la Figura 2, es bastante más intuitivo y simple construir un algoritmo o trozo de código quereconozca si un nombre de variable es correcto. El trozo de seudo-código siguiente muestra como se podría construir un programa para reconocer si una cadena corresponde a una variable de Pascal o no.

4

IIS340 : Teoría de Autómatas y Lenguajes Formales

Capítulo 1

estado = 1; símbolo = siguiente_simbolo(ENTRADA); while fin_entrada do { switch estado do { 1: if (simbolo_es_letra(simbolo))...