introduccin a la teoria de lenguajes formales

Departamento de Tecnologías de la Información

Tema 1
Introducción

Ciencias de la Computación e Inteligencia Artificial

Tema 1: Introducción

Índice

1.1. Definiciones.
1.2 Un poco de historia
1.3. Lenguajes, Gramáticas y Autómatas

2

Teoría de Autómatas y Lenguajes Formales

Tema 1: Introducción

Índice

1.1. Definiciones.
1.2 Un poco de historia
1.3. Lenguajes,Gramáticas y Autómatas

3

Teoría de Autómatas y Lenguajes Formales

Tema 1: Introducción

1.1 Definiciones

• Lenguaje:
– Forma de representar información basada en un conjunto

finito de signos o símbolos

• Alfabeto:
– Conjunto de símbolos que forman parte de un lenguaje

• Sentencia o palabra o fórmula bien formada:
– Secuencia de símbolos correcta.

• Lenguaje formal:
–Lenguaje descrito mediante un formalismo matemático
4

Teoría de Autómatas y Lenguajes Formales

Tema 1: Introducción

1.1 Definiciones

• Computar:
– Procesar información

• Modelo de computación
– Máquina abstracta que toma como entrada una secuencia

de símbolos y los procesa
– Dependiendo del modelo, el resultado del cómputo
puede ser :
• Una secuencia de acciones
• Unasalida expresada en un cierto lenguaje
• Una respuesta de aceptación o rechazo de la entada
5

Teoría de Autómatas y Lenguajes Formales

Tema 1: Introducción

1.1 Definiciones

• Autómata:
– Modelo de computación

– Maquina de estados
– El funcionamiento de la máquina se basa en transiciones
de estados
– Las transiciones están provocadas por la lectura de los
símbolos de entrada

6Teoría de Autómatas y Lenguajes Formales

Tema 1: Introducción

1.1 Definiciones

• Informática:
– Ciencia aplicada que abarca el estudio y aplicaciones del

tratamiento automático de la información

• Informática teórica:
– Disciplina que estudia las capacidades de los modelos de
computación y sus límites, así como el tipo de problemas
que pueden tratar y la eficiencia con laque pueden ser

tratados.

7

Teoría de Autómatas y Lenguajes Formales

Tema 1: Introducción

Índice

1.1. Definiciones.
1.2 Un poco de historia
1.3. Lenguajes, Gramáticas y Autómatas

8

Teoría de Autómatas y Lenguajes Formales

Tema 1: Introducción

1.2 Un poco de historia

• Lógica matemática
Friedrich Ludwig Gottlob Frege

– Nacido en Wismar (Alemania) en 1848
–Muerto en Bad Kleinen en 1945
– Profesor en la Universidad de Jena
– En 1879 publicó Conceptografía (Begriffsschrift)
– Desarrollo de la lógica de primer orden
(operadores and, or, not, implicación, para-todo, existe)
– La notación que utilizaba era bastante complicada

9

Teoría de Autómatas y Lenguajes Formales

Tema 1: Introducción

1.2 Un poco de historia

• Lógica matemáticaGiuseppe Peano

– Nacido en Spinetta (Italia) en 1858
– Muerto en Turín e 1932
– Profesor en la Universidad de Turín
y en la Academia Militar Real
– Matemático y filósofo, propuso la notación actual de la
lógica y estudió los principios de la matemática.
– Formulario, enciclopedia con todas las fórmulas y

teoremas conocidos en matemáticas
10

Teoría de Autómatas y Lenguajes FormalesTema 1: Introducción

1.2 Un poco de historia

• Lógica matemática
Bertrand Russell (1872-1970)

– Conoce a Peano en el congreso de Filosofía
de París (1900)
– Publica Principia Mathematica en 1910, 1912,
1913.
Alfred North Whitehead (1861-1947)

– Profesor en las universidades de Londres,
Cambridge y Harvard
– Fue profesor de Russell y escribió con él los
Principia MathematicaTeoría de Autómatas y Lenguajes Formales

11

Tema 1: Introducción

1.2 Un poco de historia

• Lógica matemática
David Hilbert (1862 – 1943)

– Profesor en la Universidad de Gottingen
– El matemático más importante del s. XX.
– Trabajos en análisis funcional, geometría,
fundamentos de física cuántica y de relatividad
general, lógica…
– Axiomatización de la geometría. Problemas de...