Automatas

Universidad de Oviedo TEORÍA DE AUTÓMATAS Escuela Universitaria de Ingeniería Técnica en Informática de Oviedo (E.U.I.T.I.O)

Capítulo 1: AUTÓMATAS, LENGUAJES Y GRAMÁTICAS REGULARES.
Capítulo 1.1. INTRODUCCIÓN. Los lenguajes son fundamentales en la Computación: mediante ellos se expresan los programas, protocolos de comunicación, etcétera. En la Computación se trabaja con los lenguajesformales. Estos lenguajes se caracterizan por poseer reglas sintácticas y semánticas rígidas, concretas y bien definidas. Por ejemplo, en los lenguajes de programación: • Reglas que indican cómo construir cadenas válidas (palabras reservadas, identificadores de variables, etcétera). • Reglas que indican cómo combinar estas cadenas para formar programas válidos. El procesamiento de los lenguajes formaleses importante en la Informática ya que se necesita traducir los programas escritos en lenguajes de alto nivel a programas en lenguaje máquina. Este proceso de traducción lo realizan los compiladores. Por otra parte, también se necesita describir de forma sintética los lenguajes, especificando mediante reglas, cómo se escriben programas sintácticamente correctos en un determinado lenguaje. Parallevar a cabo estos procesos disponemos de las siguientes herramientas: • Descriptoras Describen las reglas de un lenguaje . Son las gramáticas y las expresiones regulares. • Reconocedoras Reconocen si un programa sigue las reglas del lenguaje . Son los autómatas.

Alberto Suárez López

Página 1

Universidad de Oviedo TEORÍA DE AUTÓMATAS Escuela Universitaria de Ingeniería Técnica enInformática de Oviedo (E.U.I.T.I.O) Capítulo 1.2. LENGUAJES FORMALES. Definición: Alfabeto: Conjunto finito y no vacío de símbolos. Por ejemplo: = { },

={

},
}

={

}

Un alfabeto es válido si no se genera ambigüedad en la formación de palabras. Por ejemplo:

={

Palabra:

,¿

ó

?

Definición: Palabra o cadena: Secuencia finita de símbolos de un alfabeto. Por ejemplo: Sea ={

} ,son palabras

=

y

=

.

Definición: Longitud de una palabra: Número de símbolos que la forman. Por ejemplo: ={ Sea • •

}:
=

=

Definición: Palabra vacía, λ : Dado un alfabeto , λ se define como la única palabra construida con símbolos del alfabeto. Aunque se represente por un carácter simple, es una palabra no un símbolo del alfabeto, es decir, λ ∉ . Definición: Universo deldiscurso, : Se compone de todas las palabras que se pueden formar con símbolos del alfabeto Se caracteriza por: • Contiene un número infinito de palabras • La palabra vacía pertenece a todos los universos Por ejemplo: Sea

.

={

},

= {λ

}.

Alberto Suárez López

Página 2

Universidad de Oviedo TEORÍA DE AUTÓMATAS Escuela Universitaria de Ingeniería Técnica en Informática deOviedo (E.U.I.T.I.O) Definición: Lenguaje sobre un alfabeto Todo subconjunto de . ,

( ):

Por ejemplo: Dos posibles lenguajes sobre • •

={ = {λ

}

={

} serían:

}

Definición: Lenguaje: Conjunto de palabras, también llamadas sentencias o cadenas, formadas por símbolos de un alfabeto. Por ejemplo: Sea el alfabeto de los símbolos ASCII. Un lenguaje sobre este alfabeto serían todasaquellas cadenas que representen identificadores válidos en Java: • Empieza con letra, , y sigue con un conjunto de cero o más letras, dígitos, o •

={

}

Por ejemplo: Se el alfabeto de todos los identificadores, signos de puntuación, palabras reservadas en Java. Un lenguaje sobre este alfabeto sería el formado por todos los programas bien construidos. Descripción de los lenguajes:Definición: Gramática: Describe la estructura de un lenguaje, proporcionando las reglas que determinan las combinaciones válidas de los símbolos del alfabeto. Definición: Expresión regular: Describen de manera declarativa las cadenas aceptables o pertenecientes a un lenguaje regular. Definición: Autómata: Mecanismo o máquinas abstractas que son dispositivos teóricos capaces de recibir, procesar y...