Teoria de automatas

TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES

NICOLÁS KOVAC NEUMANN (Revisado Julio/2005)

TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES
A 2

T 0

1 L 4

F 3

1

TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES

NICOLÁS KOVAC NEUMANN (Revisado Julio/2005)

Breve comentario introductorio

Estos apuntes no quieren (ni mucho menos) sustituir los que impartirá el profesor de la asignatura.Sirven únicamente como una especie de "bastón" a la hora de estudiar la asignatura. Fueron tomados en el Curso 2003/2004 y los he intentado organizar de alguna forma para poder pasarlos a ordenador y posteriormente ponerlo a disposición de la gente. Es muy posible que encuentren más de una errata, estos apuntes fueron tomados por mí en clase, por lo que me he podido equivocar hasta copiando de lapizarra. De ser así ruego me lo comuniquen para corregirlo lo antes posible. He obviado pasar el tema 0 del curso, que es una introducción al C++, porque en mi opinión no tienen nada que ver con el contenido real de la asignatura, y quiero centrarme estrictamente en el contenido de la materia. Los títulos en rojo anuncian el comienzo de un nuevo tema, que explicaré hasta que aparezca otro título enrojo o se termine el temario. Los títulos en azul corresponden a subapartados de un determinado tema, que también explico a continuación. Def: corresponde a una definición de algún término o términos, que aparecen subrayados. Teor: corresponde al enunciado de algún teorema. Dem: implica el inicio de una demostración. Agradecimientos a: David Taima Hernández por la notable mejora de los dibujos.Espero que estos apuntes les sirvan de algo... un saludo. Cualquier cosa que me quieran comunicar, sean erratas, comentarios, etc., lo pueden hacer a la siguiente dirección de correo: NKNeumann@gmail.com

2

TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES

NICOLÁS KOVAC NEUMANN (Revisado Julio/2005)

TEMARIO DE LA ASIGNATURA

Tema 1: Conceptos Previos Tema 2: Conceptos Básicos Tema 3: Lenguajesregulares y Autómatas Finitos Tema 4: Gramáticas. Lenguajes Independientes del Contexto Tema 5: Máquinas de Turing Tema 6: Resolubilidad

3

TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES

NICOLÁS KOVAC NEUMANN (Revisado Julio/2005)

Tema 1

Conceptos Previos.
Lógica Proposicional.
• Equivalencia P ≡ Q Significa que P es equivalente a Q, siempre que P es cierto ⇒ Q es cierto, y siempre que Pes falso ⇒ Q es falso. P. ej: • "3 5 es entero" ≡ "Ν es finito" (ambas falsas)

Negación (p → ¬p)

Tabla de verdad p ¬p F T T F (F = False, T = True) Tabla de verdad p q p∧q F F F F T F T F F T T T Tabla de verdad p q p∨q F F F F T T T F T T T T

•

Conjunción (p ∧ q)

•

Disyunción (p ∨ q)

•

Condicional (p → q) Cuando hablamos de una proposición condicional, de la forma p → q, a"p" se le llama hipótesis o antecedente, y a "q" se le llama consecuente o conclusión. Tabla de verdad p q p→q F F T F T T T F F T T T

4

TEORÍA DE AUTÓMATAS Y LENGUAJES FORMALES

NICOLÁS KOVAC NEUMANN (Revisado Julio/2005)

•

Recíproca (q → p) La tabla de verdad se saca fácilmente viendo el ejemplo anterior

•

Contrapuesta (¬q → ¬p)

Tabla de verdad p q ¬q → ¬p F F T F T T T FF T T T

Como se puede apreciar, la Contrapuesta es equivalente a la Condicional.
bicondicional

Si (p → q) ∧ (q → p) = p ↔ q Es equivalente a decir, p sii (si y sólo si) q. Si p y q son equivalentes, entonces p ↔ q es una tautología. Def: Def: Una tautología es una proposición siempre cierta. Una contradicción es una proposición siempre falsa. Si p → q es una tautología, se escribe p ⇒ q Sip ↔ q es una tautología, se escribe p ⇔ q Def: Se llama p(x) a una frase abierta o función proposicional, donde "x" es la variable proposicional. P. ej.: x² - 1 = 0. Esta ecuación depende de la variable "x". Def: Se llama "Conjunto de significados de una variable" al conjunto de entidades que pueden sustituir a las variables. P. ej.: Sea A = {1, 2, 3}. ¿Existe algún elemento de A que haga...