Se prohíbe la reproducción total o parcial de este documento, excepto para uso privado de los alumnos de la asignatura Teoría de Autómatas I de la UNED y los alumnos de asignaturas equivalentes de otras universidades

Teoría de Lenguajes y Autómatas Conceptos y teoremas fundamentales http://www.ia.uned.es/asignaturas/automatas-1/

Angeles Manjarrés Riesco Dpto. Inteligencia Artificial UNED

Preliminares Autómata Máquina teórica capaz de realizar computaciones, utilizada en la teoría de la computación para el reconocimiento de patrones. Gramática Descripción de la estructura de las cadenas de un lenguaje. Gramática formal estructurada por frases Gramática que se describe mediante reglas de reescritura. Definición formal Cuádrupla G = (V,T,S,R) con V : conjunto finito de símbolos básicos (terminales) T : " " " " que nombran construcciones del lenguaje (no terminales) S : símbolo de inicio (∈T) R : conjunto finito de reglas de reescritura descripción descendente: → ( debe contener al menos un no terminal) Regla lambda es aquella cuyo lado derecho coincide con λ (cadena vacía). Derivar una cadena es aplicar reglas sustituyendo lado izquierdo por derecho hasta llegar a una secuencia de símbolos terminales. Lenguaje generado por una gramática Conjunto de cadenas derivadas de dicha gramática. Compilador Programa de ordenador que realiza la traducción de un lenguaje. Se utiliza para traducir el código fuente de un programa a código ejecutable directamente por un ordenador (programa objeto). Analizador léxico Parte de un compilador que reconoce la secuencia de símbolos básicos o bloques de construcción individuales del lenguaje que traduce, produciendo una cadena de componentes léxicos (tokens) a partir del código fuente. Analizador sintáctico Parte de un compilador que analiza el patrón de componentes léxicos producido por el analizador sintáctico para identificar estructuras del lenguaje. Generador de código Parte de un compilador que traduce el resultado producido por el analizador sintáctico a un programa objeto.

2

Autómatas finitos y lenguajes regulares Definiciones Definición 1 : Autómata finito determinista 1.1 Definición formal Quíntupla M= (S, Σ, d , ι, F) con S : conjunto finito de estados Σ : alfabeto de la máquina d : función de transición SxΣ →S ι : estado inicial, ι ∈S F : conjunto de estados de aceptación, F ⊆ S d (p,x) = q ⇔ M pasa del estado p al q al leer el símbolo x 1.2 M reconoce una cadena x1 x2 ... xn ⇔ ∃ una serie en S, s0, s1 ... sn con s0 = ι sn ∈F d (sj-1, xj) = Sj, j ∈ [0, n] 1.3 M reconoce un lenguaje si reconoce exclusivamente la colección de cadenas de dicho lenguaje. Se deduce que... - Todo autómata finito determinista definido para un alfabeto Σ con n símbolos debe contener al menos n transiciones. - Un autómata finito determinista acepta la cadena vacía si y sólo si su estado inicial es estado de aceptación. Definición 2 : Diagrama de transiciones Diagrama que representa un autómata finito en términos de un grafo. Consiste en una colección finita de símbolos (que representan a los estados), que se pueden rotular con fines de referencia, conectados con flechas que reciben el nombre de arcos (que representan a las transiciones). Cada arco se etiqueta con un símbolo o categoría de símbolos que podría presentarse en la cadena de entrada que el autómata analiza. Uno de los estados se distingue con un apuntador y representa el estado inicial. Los denotados con círculos dobles designan estados en los cuales se ha reconocido una cadena válida (estados de aceptación). Habitualmente en estos diagramas sólo se representan las transiciones que conducen al reconocimiento de alguna cadena, considerándose implícito un denominado "estado de captación global", donde se entiende que llegan los arcos omitidos. 2.1 Diagrama de transiciones completamente definido (o estrictamente determinista) Diagrama que representa todos los estados y transiciones de un autómata, sin omisión alguna.

3

Se deduce que... Si un diagrama de transiciones completamente definido representa un autómata finito determinista, de cada uno de sus nodos sale un arco por símbolo y sólo uno. Definición 3 : Tabla de transiciones Matriz bidimensional que representa un autómata finito determinista, tal que cada fila i representa un estado, cada columna j un símbolo del alfabeto y cada celda (i,j) contiene el nombre del estado que alcanza el autómata cuando se encuentra en el estado i y lee el símbolo Se deduce que... A partir tanto de la tabla de transiciones como del diagrama de transiciones de un autómata finito determinista se derivan fácilmente rutinas de analizador léxico para el lenguaje aceptado, reducidas a un sencillo proceso de consulta de dicha tabla o a la simulación del funcionamiento del autómata, respectivamente. Definición 4:Autómata Finito no determinista 4.1 Definición formal Quíntupla M = (S, ∑ , r , ι , F) S : conjunto finito de estados Σ : alfabeto de la máquina ρ : producto cartesianso ρ ⊆ SxΣxS ι : estado inicial, ι ∈S F : conjunto de estados de aceptación F ⊆ S

ρ no es una aplicación ⇒ ∃ transiciones inciertas  (p,x,r) ∈ ρ , (p,x,s) ∈ ρ, r ≠ s 4.2 M reconoce una cadena si es "posible" que su análisis deje a la máquina en un estado de aceptación. Definición 5: Gramática regular Se caracteriza mediante reglas de reeescritura cuyo lado izquierdo consiste en un símbolo no terminal, y cuyo lado derecho consiste en un símbolo terminal seguido de un símbolo no terminal, o bien en un símbolo terminal, o bien en λ. 5.1 Un lenguaje regular es un lenguaje generado por una gramática regular. Definición 6 : Expresión regular Siendo p y q expresiones regulares, es una expresión regular de un alfabeto Σ :

∅ cada símbolo de Σ p∪q p °q p* cualquier combinación de p, q, símbolos de Σ , λ y ∅ mediante ∪ , ° y * 6.1 Una expresión regular representa un lenguaje L( r ) de Σ de modo que:

4

L(p ∪ q) = L(p) ∪L(q) L(p ° q) = L(p) ° L(q) L(p*) = L(p)*

Teoremas Teorema 1 El conjunto de lenguajes reconocidos por autómatas finitos no deterministas coincide con el conjunto de lenguajes reconocidos por autómatas finitos deterministas. Teorema 2 El conjunto de lenguajes regulares coincide con el conjunto de lenguajes reconocidos por autómatas finitos. 2.1 Para todo lenguaje regular existe una gramática regular que lo genera que puede expresarse mediante reglas de reescritura en cuyos lados derechos nunca aparezca en solitario un símbolo terminal. Teorema 3 El conjunto de lenguajes reconocidos por autómatas finitos coincide con el conjunto de lenguajes representados por expresiones regulares. 3.1 Todos los lenguajes con un número finito de cadenas son regulares. 3.2 El conjunto de cadenas aceptadas por un autómata finito puede ser infinito. Teorema 4 Existen lenguajes no regulares. Teorema 5 La unión de un conjunto finito de lenguajes regulares es un lenguaje regular. Teorema 6 La concatenación de un conjunto finito de lenguajes regulares es un lenguaje regular. Teorema 7 La estrella de Kleene de un lenguaje regular es un lenguaje regular. 7.1 La estrella de Kleene de un lenguaje no regular puede ser regular

5

Autómatas de pila y lenguajes independientes del contexto Definiciones Definición 7 : Autómata de pila Autómata que extiende la potencia reconocedora de lenguajes del autómata finito añadiendo una memoria interna tipo pila ("contador de símbolos") y proporcionando operaciones de lectura/escritura sobre ella. 7.1 Definición formal Séxtupla M = (S,Σ ,Γ ,T,ι ,F), con S : conjunto de estados Σ: alfabeto de símbolos de entrada Γ: alfabeto de la pila Γ ⊆ (Σ ∪  # (pilavacía),otros indicadores ) T : conjunto de transiciones (p,x,s;q,y) ⊆ SxΣxΓxSxΓ ι : estado inicial ∈ S F :conjunto de estados de aceptación ⊆ S (p,x,s;q,y) ⇔ el autómata pasa del estado p al q: leyendo x de la cadena de entrada leyendo s de la pila depositando y en la pila 7.2 M reconoce una cadena si "puede" llegar a un estado de aceptación al leer la cadena (transiciones no deterministas). 7.3 M reconoce un lenguaje si acepta exclusivamente las cadenas de dicho lenguaje. Se deduce que... El espacio real de estados de M es el producto S x configuraciones de pila ( ∞ estados). Definición 8 : Autómata de pila determinista Autómata de pila M = (S,Σ ,Γ ,T,ι ,F), tal que para cada tripleta (p,x,y) en SxΣxΓ existe una y sólo una transición en T de la forma (p,u,v ;q,z), donde (u,v) está en {(x,y),(x,λ),(λ,y),(λ,λ)}, q está en S y z está en Γ. Se deduce que... El determinismo y el vaciado de pila previa aceptación de las cadenas son propiedades interesantes de los autómatas para el diseño de compiladores, ya que previenen problemas de saturación de memoria. Definición 9 : Gramática independiente del contexto Se caracteriza mediante reglas de reeescritura cuyo lado izquierdo consiste en un único símbolo no terminal, y cuyo lado derecho no está sujeto a ninguna restricción.

6

9.1 Un lenguaje independiente del contexto es un lenguaje generado por una gramática independiente del contexto. Se deduce que... Cada regla de reeescritura de una gramática independiente del contexto puede aplicarse sin importar el contexto donde se encuentre el símbolo no terminal que reescribe. Definición 10 : Forma normal de Chomsky Forma de una gramática independiente del contexto que se caracteriza mediante reglas de reeescritura cuyo lado derecho consiste en un solo símbolo terminal o exactamente dos no terminales. Definición 11: Principio de preanálisis Técnica utilizada en la construcción de analizadores sintácticos que consiste en observar los símbolos siguientes de la cadena analizada sin llegar a leerlos. Posibilita el diseño de analizadores a partir de autómatas de pila no deterministas, para el reconocimiento de lenguajes independientes del contexto. Definición 12 : Analizadores sintácticos predictivos o descendentes LL(k) Analizadores que preanalizan k símbolos de la cadena de entrada ; diseñados a partir de un automata de pila que reconoce cadenas simulando derivaciones por la izquierda. Definición 13 : Analizadores sintácticos ascendentes LR(k) Analizadores que preanalizan k símbolos de la cadena de entrada ; diseñados a partir de un automata de pila no determinista que reconoce cadenas simulando derivaciones por la derecha. Se deduce que... - Los analizadores LR(k) reconocen los lenguajes independientes del contexto deterministas. - La potencia de los analizadores LL(k) / LR(k) aumenta con el valor de k, esto es, si Lk es el conjunto de lenguajes que pueden ser tratados mediante analizadores sintácticos del tipo LL(k) / LR(k), Lk ⊆ Lk+1 para todo k≥1.

Teoremas Teorema 8 El conjunto de lenguajes reconocidos por autómatas de pila no deterministas ⊂ al conjunto de lenguajes reconocidos por autómatas de pila deterministas (el requisito de determinismo reduce el poder del autómata). Teorema 9 El conjunto de lenguajes reconocidos por autómatas de pila deterministas ⊂ al conjunto de lenguajes reconocidos por autómatas de pila deterministas que vacían siempre su pila antes de llegar a un estado de aceptación (el requisito de vaciado de pila reduce el poder del autómata).

7

9.1 Para todo autómata de pila que acepta cadenas sin vaciar su pila existe otro autómata de pila que reconoce el mismo lenguaje y vacía siempre su pila antes de llegar a un estado de aceptación. Teorema 10 Lema de bombeo: En todo lenguaje independiente del contexto que contiene un número infinito de cadenas existe una cadena de la forma svuwt, donde s,v,u,w y t son subcadenas, por lo menos una de v y w no vacía, y svnuwnt está en lenguaje para cada n∈ N+. Teorema 11 El conjunto de los lenguajes reconocidos por autómatas de pila coincide con el conjunto de lenguajes independientes del contexto. Teorema 12 Toda gramática independiente del contexto que no genere la cadena vacía puede expresarse en la forma normal de Chomsky. Teorema 13 El conjunto de lenguajes independientes del contexto incluye al conjunto de los lenguajes regulares. 13.1 Para todo lenguaje regular existe una autómata de pila que lo reconoce. 13.2 Una gramática independiente del contexto con una sola regla para cada no terminal siempre genera un lenguaje regular. Teorema 14 La unión de un conjunto finito de lenguajes independientes del contexto es un lenguaje independiente del contexto. 14.1 El complementario de un lenguaje independiente del contexto determinista es independiente del contexto determinista. 14.2 El complementario de un lenguaje independiente de contexto no regular nunca es regular. 14.3 La intersección de lenguajes independientes de contexto no regulares puede ser regular. Teorema 15 La concatenación de un conjunto finito de lenguajes independientes del contexto es un lenguaje independiente del contexto. Teorema 16 La estrella de Kleene de un conjunto finito de lenguajes independientes del contexto es un lenguaje independiente del contexto.

8

Máquinas de Turing y lenguajes estructurados por frases Definiciones Definición 14 : Máquina de Turing Clase más general de autómata, que representa la máquina abstracta más potente hasta ahora definida. Se diferencia del autómata finito y del autómata de pila en que su cabeza lectora puede retroceder, y en que puede escribir sobre la cinta donde aparecen registrados los datos que procesa, utilizándola como área de almacenamiento auxiliar. 14.1 Definición formal de Máquina de Turing Determinista Séxtupla M = (S, ,Σ, Γ, δ, ι, h) con S : colección finita de estados ι : estado inicial ∈S h : estado de parada ∈ S Σ : alfabeto de la máquina (símbolos ≠ ∆) Γ : símbolos de la cinta de la máquina Γ = Σ ∪ {marcas especiales, ∆} δ: función de transición δ: (S’ x Γ) → S x (Γ ∪ { L,R }) - operaciones de escritura: δ (p,x) = (q,y) - “ “ de movimiento: δ (p,x) = (q,L) δ (p,x) = (q,R) S’ = S - h (estados de no parada) p,q ∈ S x,y ∈ Σ L movimiento de la cabeza de lectura hacia la izquierda R movimiento de la cabeza de lectura hacia la derecha Se deduce que... Ciertos problemas resolubles por máquinas de Turing no pueden ser resueltos por un computador, ya que un computador tiene una memoria finita. Para que un problema resoluble mediante una máquina de Turing sea resoluble mediante un computador es necesario que su complejidad espacial quede dentro de los límites de la memoria del computador. 14.2 Modo de operación normal de una Máquina de Turing Consiste en ejecutar transiciones hasta posiblemente llegar a un estado de parada (también puede realizar cálculos indefinidamente). 14.3 Terminación anormal de una Máquina de Turing Tiene lugar cuando la cabeza de lectura rebasa el extremo izquierdo de la cinta.

9

14.4 Una Máquina de Turing analiza una cadena 1º) registrando la cadena a partir de la segunda celda de su cinta 2º) sitúando su cabeza de lectura en el extremo izquierdo 3º) arrancando la máquina desde el estado inicial hasta alcanzar un estado de parada 14.5 Una Máquina de Turing acepta una cadena Dos posibles criterios: a) cuando se detiene en la configuración ∆Y∆∆.. b) cuando simplemente se detiene Se deduce que... - Una máquina de Turing es capaz de aceptar una cadena sin leer todos sus símbolos. Definición 15. Bloques básicos de construcción Máquinas de Turing elementales mediante cuya combinación se expresan máquinas de Turing más complejas. 15.1 Máquina R Mueve la cabeza una celda hacia la derecha. 15.2 Máquina L Mueve la cabeza una celda hacia la izquierda. 15.3 Máquina x Escribe una x. 15.4 Máquina Rx Recorre la cinta a la derecha de su posición inicial en busca de una celda que contenga el símbolo x. Si lo encuentra se detiene, en caso contrario continua la búsqueda eternamente. 15.5 Máquina R¬x Recorre la cinta a la derecha de su posición inicial en busca de una celda que contenga un símbolo que no sea x. Si lo encuentra se detiene, en caso contrario continua la búsqueda eternamente. 15.6 Máquina Lx Recorre la cinta a la izquierda de su posición inicial en busca de una celda que contenga el símbolo x. Si lo encuentra se detiene, en caso contrario continua la búsqueda eternamente. 15.7 Máquina L¬x Recorre la cinta a la izquierda de su posición inicial en busca de una celda que contenga un símbolo que no sea x. Si lo encuentra se detiene, en caso contrario continua la búsqueda eternamente. 15.8 Máquina SR Desplaza una celda a la derecha la cadena de símbolos que no están en blanco y que se encuentran a la izquierda de la celda actual.

10

15.9 Máquina SL Desplaza una celda a la izquierda la cadena de símbolos que no están en blanco y que se encuentran a la derecha de la celda actual. Definición 16. Máquina de Turing No Determinista Máquina de Turing M = (S, ,Σ, Γ, δ, ι, h) tal que δ no es una función, es decir, más de una transición es posible para cada par estado-símbolo: δ ⊆ ((S - { h }) xΓ) x(S x (Γ∪ { L, R})). 16.1 Una Máquina de Turing No Determinista acepta una cadena si es posible que llegue al estado de parada al iniciar sus cálculos con la cadena como entrada. Se deduce que... - Cuando una máquina de Turing (determinista o no determinista) examina una cadena existen cuatro posibles resultados: a) la máquina se detiene en el estado de parada b) no llega a detenerse nunca c) se detiene sin haber llegado a un estado de parada (abandona sus cálculos por no estar completamente definida: es no determinista) d) termina de forma anormal (es decir, la cabeza lectora se desplaza a la izquierda de la primera celda de la cinta) Definición 17. Lenguaje estructurado por frases Es aquél cuya estructura de cadenas puede analizarse mediante una jerarquía de estructuras de frases o, dicho de otro modo, aquél que puede definirse mediante una gramática estructurada por frases. Definición 18. Codificación binaria de una Máquina de Turing Sistema de representación basado en las siguientes denotaciones: Estados: ι ≡ 0 h≡ 00 j ≡ 0 j Γ: símbolo i ≡ 0 i+2 ∆ ≡ “cadena vacía” δ: L≡0 R ≡ 00 (p,x,q,y) ≡ p1q1x1q1y Una máquina de Turing se denota por la sucesión de sus posibles transiciones: - separadas por un 1 (más un 1 al principio y final de la lista) - ordenadas por estado y símbolo actual. Definición 19. Máquina de Turing Universal o Programable Máquina de Turing capaz de simular el procesamiento de cualquier otra máquina de Turing. Definición 20. Lenguaje Decidible o Recursivo Lenguaje para el cual existe una máquina de Turing que puede decidir si una cadena se encuentra o no en el lenguaje, en vez de limitarse a aceptar cadenas que pertenecen al mismo. Definición 21. Lenguaje Aceptable o Recursivamente Enumerable Lenguaje para el cual existe una máquina de Turing que reconoce sus cadenas.

11

Definición 22. Problema de la parada Nombre por que se conoce a la incapacidad de decidir mediante una máquina de Turing si una cadena de unos y ceros es la versión codificada de una máquina de Turing Autoterminante. Definición 23. Máquina de Turing Autoterminante Máquina de Turing que se detiene cuando la cadena de entrada representa su propia codificación binaria (aunque puede también deterse en otros casos).

Teoremas Teorema 17 (axioma) Tesis de Turing: La máquina de Turing define el límite máximo de un proceso computacional (es más potente que cualquier computador, al carecer de restricciones de almacenamiento). Teorema 18. Equivalencia entre criterios de aceptación de una máquina de Turing: Si existe una máquina de Turing que sólo se detiene con las cadenas de un lenguaje, entonces existe una máquina de Turing que sólo se detiene con las cadenas de dicho lenguaje y con la configuración de cinta ∆Y∆∆. Teorema 19. El conjunto de lenguajes reconocidos por máquinas de Turing de una cinta no deterministas es equivalente al conjunto de lenguajes reconocidos por máquinas de Turing deterministas de una cinta, y al conjunto de lenguajes reconocidos por máquinas de Turing de varias cintas. Teorema 20. El conjunto de lenguajes estructurados por frases es equivalente al conjunto de lenguajes reconocibles por máquinas de Turing. Teorema 21. Para todo alfabeto existen lenguajes no estructurados por frases. 21.1. Ningún proceso algorítmico reconoce lenguajes sin base gramatical (potencia máxima de la máquina de Turing). Existen pues lenguajes no analizables sintácticamente por un computador. Teorema 22. El conjunto de lenguajes independientes del contexto incluye al conjunto de los lenguajes regulares. 22.1 Una máquina de Turing Universal es capaz de decidir cualquier lenguaje independiente del contexto. Teorema 23. La unión de un número finito de lenguajes estructurados por frases es un lenguaje estructurado por frases.

12

23.1 El complementario de un lenguaje estructurado por frases no siempre es estructurado por frases. 23.2 El complementario de un lenguaje estructurado por frases decidible, es estructurado por frases. 23.3 La intersección de un conjunto finito de lenguajes decidibles es decidible. 23.4 La intersección de dos lenguajes estructurados por frases es un lenguaje estructurado por frases. 23.5 El complementario de un lenguaje decidible no siempre es independiente del contexto. 23.6 La unión de un conjunto finito de lenguajes decidibles es un lenguaje decidible 23.7 La unión de un lenguaje independiente del contexto no regular con un lenguaje estructurado por frases puede ser regular Teorema 24 La concatenación de un conjunto finito de lenguajes estructurados por frases es un lenguaje estructurado por frases. Teorema 25 La estrella de Kleene de un lenguaje estructurado por frases es un lenguaje estructurado por frases.

13