Teoría De Autómatas Y Lenguajes Formales

Teoría de Autómatas y Lenguajes Formales Capítulo 1: “Introducción”
Holger Billhardt holger.billhardt@urjc.es

Introducción
Teoría de Autómatas y Lenguajes formales es un “repaso” a la informática teórica. La informática teórica:
se ha desarrollado en base a la confluencia de campos en aparencia muy distintos:
Investigación acerca de Fundamentos Matemáticos, Teoría de Máquinas, Lingüística,…

Ciencia multidisciplinar que se apoya en que los mismos fenómenos pueden actuar y servir de fundamento en áreas totalmente desconectadas (aparentemente).
Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

Universidad Rey Juan Carlos

2

1

Introducción
Pilares de la informática teórica:
Autómatas / máquinas secuenciales Lenguajes y gramáticasMáquinas abstractas y algoritmos

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

3

Autómatas / Máquinas secuenciales
Eslabón de la informática teórica que proviene de la Ingeniería Eléctrica. 1938 – Claude Elwood Shannon: “A symbolic Analysis of relay and switching circuits”
Aplicación de la lógica matemática a loscircuitos combinatorios y secuenciales.

Sus ideas desarrollaron la Teoría de los autómatas finitos y máquinas secuenciales
Un autómata es un dispositivo abstracto que es capaz de recibir información, cambiar de estado y transmitir información.
Universidad Rey Juan Carlos Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas 4

2

Autómatas / Máquinassecuenciales
Un autómata puede describir de forma formal el funcionamiento de un sistema
Ejemplo: interruptor
pulsar off on

inicio

pulsar

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

5

Autómatas / Máquinas secuenciales
Un autómata es un modelo abstracto de una computadora digital
Lee símbolos en la entradaProduce símbolos en la salida Tiene una unidad de control que puede estar en uno de sus posibles estados internos Puede cambiar de los estados internos en función de la entrada Puede tener algún tipo de memoria

Autómatas transductores / generadores / aceptadores
Entrada Unidad de Control Memoria
Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

SalidaUniversidad Rey Juan Carlos

6

3

Lenguajes y Gramáticas
Segundo eslabón: Lingüística (campo tradicionalmente considerado no científico). Años 50 – Avram Noam Chomsky
Teoría de las Gramáticas Transformacionales
Base de la Lingüística Matemática Proporcionó una herramienta que no sólo podía aplicarse a los lenguajes naturales, sino que facilitaba el estudio y formalización de los lenguajesde ordenador que aparecían en aquella época.

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

7

Lenguajes y Gramáticas
Cualquier comunicación se realiza mediante cadenas de símbolos que corresponden a un lenguaje. Lenguajes son conjuntos de cadenas de símbolos (palabras, oraciones, textos o frases) El estudio de loslenguajes se reduce, básicamente, a:
Sintaxis: (gramática)
define las secuencias de símbolos que forman cadenas válidas de un lenguaje Gramática: Descripción formalizada de las oraciones de un lenguaje. Una gramática genera o describe un lenguaje.

Semántica:
significado de las cadenas que componen un lenguaje

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales IngenieríaTécnica en Informática de Sistemas

8

4

Lenguajes y Gramáticas
Ejemplo 1:
Semántica:
A es un número natural.

Diferente sintaxis en diferentes lenguajes:
A is a natural number. A : Natural; 0100000100000001

Universidad Rey Juan Carlos

Teoría de Autómatas y Lenguajes Formales Ingeniería Técnica en Informática de Sistemas

9

Lenguajes y Gramáticas
Ejemplo 2:
Sintaxis:...