CIS 262 languages - CIS 262-UPENN

Introducción a la Teoría de la Computación

Jean Gallier Departamento de Informática y Ciencias de la Informaciónuniversidad de Pensilvania, Filadelfia, Pensilvania, 19104, USAe-mail:[email protected]

©c Jean Gallierpor favor, no presente sin permiso del autor

Marzo 5, 2020

4 ÍNDICE

6.4 El Lema de Bombeo
6.5 Un Algoritmo Rápido para Verificar la Equivalencia de Estado
7 Gramáticas Y Lenguajes Libres De Contexto
7.1 Gramáticas Libres de Contexto
7.2 Derivaciones y Lenguajes Libres de Contexto
7.3 Formas Normales para Gramáticas Libres de Contexto
7.4 Los Lenguajes Regulares son Libres de Contexto
7.5 Producciones Inútiles en Gramáticas Libres de Contexto
7.6 La Forma Normal de Greibach
7.7 Menos Puntos Fijos
7.8 Lenguajes Sin Contexto como Menos Puntos Fijos
7.9 Menos Puntos Fijos y la Forma Normal de Greibach
7.10 Dominios de Árbol y Árboles de Gorn
7.11 Árboles de Derivaciones
7.12 Lema de Ogden
7.13 Autómatas de Empuje
7.14 De Gramáticas Libres de Contexto A PDA
7.15 De PDA A Gramáticas Libres de Contexto
7.16 El Teorema de Chomsky-Schutzenberger
8 Una Encuesta de Métodos de Análisis de RR
8.1 LR(0)-Autómatas característicos
8.2 Analizadores de cambio/Reducción
8.3 Cálculo del PRIMER
8.4 La Intuición Detrás del Algoritmo de Cambio/Reducción
8.5 El Método Gráfico para Calcular Puntos Fijos
8.6 Cálculo de SEGUIMIENTO
8.7 AlgorithmTraverse
8.8 Más onLR(0)-Autómatas característicos
8.9 LALR (1)-Conjuntos de Lookahead
8.10 Computación PRIMERO, SEGUIMIENTO, etc. en presencia deǫ-Reglas
8.11 LR (1) – Autómatas característicos

Introducción

La teoría de la computación se refiere a algoritmos y sistemas algorítmicos: su diseño y representación, su integridad y su complejidad.

El propósito de estas notas es introducir algunas de las nociones básicas de la teoría de la computación, incluyendo conceptos de lenguajes formales y teoría de autómatas, la teoría de la computabilidad, algunos fundamentos de la teoría de funciones recursivas, y una introducción a la teoría de la complejidad. Otros temas, como la corrección de los programas, no se tratarán aquí (¡no hay tiempo suficiente!).

Las notas se dividen en tres partes. La primera parte está dedicada a las lenguas formales y a los autómatas. La segunda parte trata de modelos de cómputo, funciones recursivas y falta de decisión. La tercera parte trata de la complejidad computacional, en particular la clase y el NP.

5

Fundamentos de la Teoría Formal del Lenguaje

2.1 Revisión de alguna Notación Matemática Básica y

N, Z, Q, R, C.

Los números naturales, N = {0, 1, 2 ,…}.

Theintegers, Z = {…,− 2 ,− 1 , 0 , 1 , 2 ,…}.

Therationals,

{

}

null

Allí, R. Números complejos, C = {a + ib / a, b∈R}.

Dado cualquier setX, el conjunto de potencia de X es el conjunto de todos los subconjuntos de Xand se denota 2X.La notación f:X→Y

denota una función con Dominio X y Rango(o dominio)Y.

graph(f) ={(x,f(x)}|x∈X}⊆X×Y

es thegraphoff.

7 8 CAPÍTULO 2. FUNDAMENTOS DE LA TEORÍA DEL LENGUAJE FORMAL

Im(f) =f(X) ={y∈Y |x x∈X, y=f(x)} Im Y

es la imagen off.

Más generalmente, ifA X X, entonces

f(A) ={y∈Y |x x∈A, y=f(x)}} Y

es la imagen(directa) de Aofa.

IfB If Y, entonces f-1(B) ={x∈X|f(x)∈B} is X

es la imagen inversa (orpullback) de B.

f-1 (B) es un conjunto; puede estar vacío incluso ifB 6 =∅.Dadas dos funciones f: X→Y y g: Y→Z, la función◦f:X→Zgiven por

(g◦f)(x) =g(f(x)) para allx∈X

es la composición de fandg.

La función idX: X→Xgiven by

idX (x) = x para allx∈X

es la función de identidad(ofX).

Una funciónf: X→Y isinyective (terminología antigua uno a uno)si para allx 1, x 2 ∈X,

iff (x 1) =f (x 2), thenx 1 = x 2 ;

equivalentemente ifx 16 = x 2, luego f(x 1 ) 6 =f (x 2 ).

Hecho: IfX 6 =soY(y soY 6=∅), una funciónf:X →Y es inyectiva iff hay una funciónr:Y →X(inversa aleft) tal que

r◦f= idX.

Nota: suryective.Una funciónf:X→Y issurjective(antigua terminologíaonto)si para ally∈Y, hay algo∈Xsuch que=f(x), ifff(X) =Y.

Hecho: IfX 6 =soY(y soY 6=∅), una funciónf:X→Y es sobreyectiva iff hay una funciones:Y →X(una sección inversa correcta) tal que

f◦s= idY.

10 CAPÍTULO 2. FUNDAMENTOS DE LA TEORÍA DEL LENGUAJE FORMAL

Una relaciónR×X×Xissymmetricif para allx,y∈X, si (x,y)∈R, entonces (y,x)∈R

Una relaciónR A X×Xis simétrica iffR− 1 R R.

GivenR X X × X(una relación onX), defineRnby

R 0 =IXRn+1=R◦Rn.

El cerrador de transferencia + ofRis dado por

R+=

⋃

n≥ 1

Rn.

Hecho.R + es la relación transitiva más pequeña que contiene R.

El cerrador flexible y transitivo∗ofRis dado por

R∗=

⋃

n≥ 0

Rn=R+IX IX.

Hecho.R∗es la relación transitiva y reflexiva más pequeña que contiene R.

Una relación R×X × X Es una relación de equivalencia si es reflexiva, simétrica y transitiva.

Hecho. La relación de equivalencia más pequeña que contiene una relaciónR×X × X es dada por

(R R R− 1 )∗.

A relationR×X × Xisantisymmetricif para allx,y∈X, if (x,y)∈Rand (y,x)∈R,thenx=y.

A relationR×X × Xis de orden aparcial si es reflexivo, transitivo y antisimético.

Un orden parcial R X X×X es un orden total si para allx,y ∈X, o bien (x,y)∈ Ror(y,x)∈R.

2.2 Alfabetos, Cadenas, Idiomas

Nuestra visión de los idiomas es que un lenguaje es un conjunto de cadenas. A su vez, una cadena es una finísima consecuencia de letras de algún alfabeto. Estos conceptos se definen rigurosamente de la siguiente manera:

Definición 2.1.AnalphabetΣ es cualquier conjunto de finitos.

2.2. ALFABETOS, CADENAS, IDIOMAS 11

A menudo escribimos Σ ={a 1 ,…, ak}. Se llaman los símbolos del alfabeto.Ejemplos:Σ = {a}Σ ={ a,b,c}Σ ={0 , 1 }Σ = {α,β,γ,δ,λ,λ,φ,ψ,ω,μ,ν,ρ,σ,η,ξ,ζ}Una cadena es una secuencia finita de símbolos. Técnicamente, es conveniente definir cadenas como funciones. Para cualquier entero≥1, let

={ 1 , 2 ,…, n},

y forn = 0, let=∅.

Definición 2.2. Dado un alfabeto Σ, astring overΣ (o simplemente una cadena) de longitud función nisany

u: →Σ.

El integern es la longitud de la stringu, y se denota como|u/. Cuando N = 0, la cadena especial u: → Σ de longitud 0 se denomina cadena vacía, o cadena nula, y se denota comoǫ.

Dado un stringu: →Σ de longitud≥1, u (i) es la i-ésima letra en el stringu. Por simplicidad de notación,nos writeuiinstead deu(i), y se denota la stringu=u(1)u(2)··· * u(n)como

u=u 1 u 2 ···de la onu,

con eachui∈Σ.

Por ejemplo, si Σ = {a, b} andu: → Σ se define tal thatu(1) =a,u(2) =b, andu(3) =a, escribiremos eu=aba.

Otros ejemplos de cuerdas son

work, fun, gabuzomeuh

Las cuerdas de longitud 1 son functionsu: →Σ simplemente recogiendo algún elemento (1) = aiin Σ.Por lo tanto, identificaremos cada symbolai∈Σ con la cadena correspondiente de longitud 1.

El conjunto de todas las cadenas sobre un alfabeto Σ, incluida la cadena vacía, se denota como Σ∗.

2.2. ALFABETOS, CADENAS, IDIOMAS 13

Para la base casen = 0, sinceu 0 = ǫ, tenemos

u 0 u = ǫu = u = u 0 = uu 0.

Para la inducción de paso, tenemos

un+1u= (unu)u por definición ofún+ = (uun)u por la hipótesis de inducción =u(unu) por la asociatividad =uun+1 por definición ofún+1.

Definición 2.4.Dado un alfabeto Σ, dado dos cadenas cualesquiera, v∈Σ∗, definimos las siguientes emociones de la siguiente manera:

u es un prefijo de viff hay algo∈Σ∗tal que

v=uy.

u es un sufijo de viff hay somex∈Σ∗tal que

v = xu.

u es una subcadena de viff hay somex, y∈Σ∗de tal manera que

v=xuy.

Decimos que u es un prefijo apropiado (sufijo, subcadena) de viffu es un prefijo (sufijo, subcadena)de vandu 6 =v.

Por ejemplo,gai es un prefijo de gabuzo,zois un sufijo de gabuzo ybuz es una subcadena de gabuzo.Recordemos que un orden parcial≤ en un conjunto es una relación binaria≤×S × S que es reflexiva, transitiva y antisimétrica.

Los conceptos de prefijo, sufijo y subcadena, definen relaciones binarias en Σ∗en el camino obvio. Se puede demostrar que estas relaciones son ordenaciones parciales.

Otro orden importante en cadenas es el orden lexicográfico (o diccionario).

Definición 2.5. Dado un alfabeto Σ = {a 1 ,…, ak} asumido totalmente ordenado tal que 1 < a 2 <···< ak, dadas dos cuerdas cualesquiera, v∈Σ∗, definimos el orden electrocográfico como sigue:







(1) ifv = uy, para somey∈Σ∗, o(2) ifu=xaiy,v=xajz,ai< aj,withai,aj∈Σ, y para somex,y,z∈Σ∗.

14 CAPÍTULO 2. CONCEPTOS BÁSICOS DE LA TEORÍA DEL LENGUAJE FORMAL

La idea es que escaneemos y visualicemos simultáneamente de izquierda a derecha, comparando el símbolo del símbolo del lenguaje con el símbolo vminv, comenzando con m= 1. Si no surge ninguna discrepancia, eso es, si el-ésimo símbolo coincide con el-ésimo símbolo vminvform = 1,…,| u/, entonces u es un prefijo de v y declaramos que precede al orden lexicográfico. De lo contrario, por un tiempo, yvagree a lo largo de un prefijo común x(posiblemente la cadena vacía), y luego hay una discrepancia casi total,lo que significa que uis del formu=xaiyandvis del formv=xajz,withai 6 =aj(andx, y, z∈Σ∗arbitrario). Entonces necesitamos romper el empate, y para hacer esto usamos el hecho de que el símbolo a 1 < a 2 <···< se supone que ak está (totalmente)ordenado, por lo que vemos cuál deai yaj viene primero, sayai< aj, y declaramos thatu=xaiyprecedesv=xajzin el orden lexicográfico.

Tenga en cuenta que los casos (1) y (2) son mutuamente excluyentes. En el caso (1), u es un prefijo ofv. En el caso(2)v6uandu 6 =v.

Por ejemplo abb, gallhagergallier.

Es bastante tedioso probar que el ordenamiento lexicográfico es de hecho un ordenamiento aparcial.De hecho, es un orden total, lo que significa que para dos cadenas cualesquiera,v∈Σ∗, eitheruv, orvu.

Todas las cuerdas de una cuerda se definen inductivamente de la siguiente manera:

ǫr=ǫ,(ua)R=auR,

donde a∈Σ andu∈Σ∗.

Por ejemplo reillag = gallierR.

Por settingu=ǫin (ua)R=auR,

sinceǫR=ǫanda=ǫa, obtenemos

aR= (ǫa)R=aǫR=aǫ=a,

namelyaR=aporque alla∈Σ.

Se puede mostrar por inducción en|v / que

(uv) R=vRuR.

Un truco útil que reduce la notación engorrosa al hacer inducción en cuerdas es la observación de que una cuerda no vacía w∈Σ∗de longitud+ 1 (n≥0) se puede escribir como

w=ua, para someu∈Σ∗y algún symbola∈Σ, con|u|=n.

16 CAPÍTULO 2. FUNDAMENTOS DE LA TEORÍA DEL LENGUAJE FORMAL

Six no es el conjunto vacío, ya queef:X→Nis una inyección si hay un sobrejectarr:N→X Tal quer◦f = idX, el setx es contable si hay un sobrejectar de Nontox.

Hecho. Se puede demostrar que un conjunto es contable si es finito o si está en biyección con N(en cuyo caso es infinito).

Veremos más adelante que N×Nis contable. Como consecuencia, el conjunto de números racionales es contable.

Un conjunto no es numerable si no es contable.

Por ejemplo,R (el conjunto de números reales) es incontable.Del mismo modo

(0,1) ={x∈R| 0 < x < 1 }

es incontable. Sin embargo, hay una biyección entre (0,1) andR (¡encuentra uno!) El conjunto 2 de todos los subconjuntos de NNI es incontable. Este es un caso especial del teorema de Cantor que se analiza a continuación.

Supongamos|Σ|=kwith Σ ={a 1 ,…, ak}. En primer lugar, observe que hay cuerdas de longitud y (kn+1-1)/(k−1) cuerdas de longitud en la mayor parte de Σ; cuando k= 1, la segunda fórmula debe ser reemplazada poryn+ 1. De hecho, ya que una cadena es una funciónu: {1 ,…, n} →Σ, el número de cadenas de longitud es el número de funciones de{ 1 ,…, n}a Σ, y desde la cardinalidad de Σ isk, hay funciones kn (esto se muestra inmediatamente por inducción onn). A continuación, el número de cadenas de longitud en mostnis

1 +k+k 2 +···+kn.

Si k = 1, este número es n+ 1, y si k ≥ 2, como la suma de una serie geométrica, es(kn+1-1)/(k−1).

Si Σ 6=∅, entonces el conjunto Σ∗de todas las cuerdas sobre Σ es infinito y contable, como ahora mostramos construyendo una biyección explícita a partir de Σ∗ontoN.

Ifk = 1 writea = a 1, y luego

{a}∗ = {ǫ, a, aa, aaa,…,un,…}.

Tenemos la biyección 7→anfromNto {a}∗.Ifk≥2, entonces podemos pensar en la cadena

u = ai 1 * * * ain

como una representación del integerv(u) en basekshifted por (kn−1)/(k−1), con

2.2. ALFABETOS, CADENAS, IDIOMAS 17

ν(u) =i 1 kn− 1 +i 2 kn− 2 +···+en− 1 de k+en

kn− 1 k− 1

(i 1, -1)kn− 1 +···+ (en− 1 -1)k+en− 1.

(y withv (ǫ) = 0), donde 1≤ij≤kforj = 1,…, n.

Lo dejamos como un ejercicio para mostrar que v: Σ∗→Nis a biyección. Encontrar de forma explícita(es decir, una fórmula) para el inverso de la visión sorprendentemente difícil.

De hecho,ν corresponde a la enumeración de Σ∗donde precede v if|u|< |v|, y precede v al orden lexicográfico if|u|=|v|. Es fácil comprobar que la aboverelación (uprecedesv) es un pedido total.

Por ejemplo, ifk = 2 y si escribimos Σ ={a,b}, entonces la enumeración comienza con

ǫ,0a, b,1 , 2 ,aa, ab, ba, bb,3 , 4 , 5 , 6 ,aaa, aab, aba, abb, baa, bab, bba, bbb7 , 8 , 9 , 10 , 11 , 12 , 13 , 14

Para obtener la siguiente fila, concatenar a la izquierda, y luego concatenar a la izquierda. Wehavev (bab) = 2· 22 + 1· 21 + 2 = 8 + 2 + 2 = 12.

funciona!

Por otro lado, si Σ 6=∅, el conjunto 2Σ ∗ de todos los subconjuntos de Σ∗(todos los idiomas) no es numerable.De hecho, podemos demostrar que no hay sobreyección de Nonto 2Σ ∗ Primero, mostraremos que no hay sobreyección de Σ∗a 2Σ∗. Este es un caso especial del teorema de Cantor.Afirmamos que si no hay sobreyección de Σ∗a 2Σ ∗ , entonces tampoco hay sobreyección de Nonto 2Σ∗.

Prueba. Supongamos por contradicción que hay un surjectiong: N→ 2 Σ ∗ . Pero, si Σ 6=∅, entonces Σ∗es infinito y contable, así tenemos la biyección v: Σ∗→N. Entonces la composición

Σ∗ ν / / N

g / / 2 Σ ∗

es una sobreyección, porque la biyección es una sobreyección, es una sobreyección, y la composición de sobreyecciones es una sobreyección, contradiciendo la hipótesis de que no hay sobreyección deσ∗a 2Σ ∗ .

2.3. OPERACIONES EN IDIOMAS 19

2.3 Operaciones en idiomas

Una forma de construir lenguajes más complejos a partir de lenguajes más simples es combinarlos usando varias operaciones. Primero, revisamos las operaciones teóricas de conjunto de unión, intersección y ejecución.

Dado algún alfabeto Σ, para dos idiomas cualesquiera L 1, L 2 sobre Σ, la unión L 1 L L 2 ofL 1andL 2 es el lenguaje

L 1 L L 2 = {w∈Σ∗ / w∈L 1 o w∈L 2}.

TheintersectionL 1 ∩L 2 ofL 1 andL 2 es el lenguaje

L 1 ∩L 2 ={w∈Σ∗|w∈L 1 y w∈L 2 }.

El diferencial 1-L 2 de L 1 y L 2 es el lenguaje

L 1-L 2 ={w∈Σ∗|w∈L 1 y w /∈L 2 }.

La diferencia también se llama complemento derelativo.

Se obtiene un caso especial de la diferencia cuando l 1 = Σ∗, en cuyo caso definimos el complemento de un idioma

L = {w∈Σ∗/w / ∈L}.

Las operaciones anteriores no utilizan la estructura de cadenas. Las siguientes operaciones usan concatenación.

Definición 2.8.Dado un alfabeto Σ, para dos idiomas cualesquiera L 1, L 2 sobre Σ, la concatenación L 1 L 2 ofL 1 y L 2 es la lengua

L 1 L 2 ={w∈Σ∗|u u∈L 1, v v∈L 2 , w=uv}.

Para cualquier idioma, definimos como sigue:

L 0 = {}}, Ln + 1 = LnL (n≥0).

Por settingn = 0 inLn + 1 = LnL, sinceL 0 = {}}, obtenemos

L 1 =L0+1=L 0 L={{} L=L,

soL 1 =L.

20 CAPÍTULO 2. Conceptos BÁSICOS DE LENGUAJE FORMAL de la TEORÍA

Las propiedades siguientes se comprueba fácilmente:

L∅=∅,∅L=∅,L{ǫ}=L{ǫ}L=L,(L 1 ∪{ǫ})L 2 =L 1 L 2 ∪L 2 ,L 1 L 2 ∪{ǫ}) =L 1 L 2 ∪L 1 ,LnL=LLn.

En general,L 1 L 26 = L 2 L 1.So hasta ahora, las operaciones que hemos introducido, excepto la complementación (sinceL= Σ∗−Lis infinita ifLis finita y Σ no vacía), conservan la finitud de las lenguas. Este no es el caso de las dos operaciones siguientes.

Definición 2.9.Dado un alfabeto Σ, para cualquier lengua más Σ, el Kleene∗ – closureL∗de la lengua

L∗ =