Llista de problemes 2

Intruccions

Els recursos útils per resoldre els exercicis d’aquest conjunt de problemes són els següents:

Vídeos de G. Godoy

• Gramáticas incontextuales
• Operaciones sobre gramáticas
• Depuración de gramáticas (1)
• Depuración de gramáticas (2)
• Depuración de gramáticas (3)

Llibres

• (Sipser 2013, \S 2.1 Content-free Grammars)
• (Cases i Màrquez 2003, \S 2 and \S 3)
• (Hopcroft, Motwani, i Ullman 2007, \S 5)

Cases, Rafel, i Lluís Màrquez. 2003. Llenguatges, gramàtiques i autòmats : curs bàsic. 2a ed. Edicions UPC.

Hopcroft, John E., Rajeev Motwani, i Jeffrey D. Ullman. 2007. Introduction to Automata Theory, Languages, and Computation. 3rd edition. Pearson Addison Wesley.

Sipser, Michael. 2013. Introduction to the theory of computation. 3rd edition. Cengage Learning.

Tots els exercicis

Exercici 1 (Només incontextual o en realitat regular?) Més endavant en el curs veurem que no existeix cap algorisme que sempre acabi i respongui la pregunta “Donada una gramàtica incontextual, genera un llenguatge regular?”.

Per a cadascuna de les gramàtiques incontextuals de sota, trobeu quin és el llenguatge generat i demostreu si és un llenguatge regular o no.

1. \left\{\begin{array}{ccl} S &\to& AB \mid CD \\ A &\to& 0A0 \mid 0 \\ B &\to& 1B1 \mid \lambda \\ C &\to& 0C0 \mid \lambda \\ D &\to& 1D1 \mid \lambda \end{array}\right.
2. \left\{\begin{array}{ccl} S &\to& aA \mid bB \mid \lambda \\ A &\to& Sa \mid Sb \\ B &\to& Sb \end{array}\right.
3. \left\{\begin{array}{ccl} S &\to& AB \\ A &\to& 0A0 \mid 1 \\ B &\to& 1B1 \mid 0 \end{array}\right.
4. \left\{\begin{array}{ccl} S &\to& 0S0 \mid 0S1 \mid \lambda \end{array}\right.
5. \left\{\begin{array}{ccl} S &\to& AB \\ A &\to& 0A0 \mid 0A1 \mid \lambda \\ B &\to& 0B \mid 1B \mid \lambda \end{array}\right.
6. \left\{\begin{array}{ccl} S &\to& A \mid B \\ A &\to& 0S0 \mid 1S1 \mid \lambda \\ B &\to& 0S1 \mid 1S0 \mid \lambda \end{array}\right.
7. \left\{\begin{array}{ccl} S &\to& A \mid B \\ A &\to& 0A0 \mid 1A1 \mid \lambda \\ B &\to& 0B1 \mid 1B0 \mid \lambda \end{array}\right.
8. \left\{\begin{array}{ccl} S &\to& aSa \mid bSb \mid X \\ X &\to& aXb \mid bXa \mid a \mid b \mid \lambda \end{array}\right.
9. \left\{\begin{array}{ccl} S &\to& WXW' \\ X &\to& aX \mid bX \mid \lambda \\ W &\to& aW \mid bW \mid \lambda \\ W' &\to& W'a \mid W'b \mid \lambda \end{array}\right.

Exercici 2 (Gramàtiques incontextuals ambigües) Demostreu que les gramàtiques següents són ambigües.

1. \left\{\begin{array}{ccl} S &\to& aSb \mid B \\ B &\to& bAa \mid bCb \mid \lambda \\ A &\to& aAbA \mid bAaA \mid \lambda \\ C &\to& Aaa \mid aAa \mid aaA \end{array}\right.
2. \left\{\begin{array}{ccl} S &\to& aU_1 \mid aS \mid bZ_1 \mid bS \\ Z_1 &\to& aU_2 \mid bF \\ U_1 &\to& bU_2 \\ U_2 &\to& bF\mid b \\ F &\to& aF \mid bF \mid a \mid b \end{array}\right.
3. \left\{\begin{array}{ccl} S &\to& AaBA \mid ABaA \mid ACA \mid AbabA \\ B &\to& bb \\ C &\to& bB \\ A &\to& aA \mid bA \mid \lambda \end{array}\right.
4. \left\{\begin{array}{ccl} S &\to& aU_1 \mid aS \mid bZ_1 \mid bS \\ Z_1 &\to& aU_2 \mid bZ_2 \\ U_1 &\to& bU_2 \\ U_2 &\to& bF \\ Z_2 &\to& aF \mid bF \\ F &\to& aF \mid bF \mid \lambda \end{array}\right.

Exercici 3 (Llenguatges de Dyck) En aquest exercici considerem el llenguatge de Dyck, és a dir, el llenguatge dels parèntesis ben formats (i algunes variants). Més concretament, donat l’alfabet \Sigma=\{(,)\}, el llenguatge de Dyck \mathsf{dyck}(1) és \mathsf{dyck}(1) =\{w\in \Sigma^* \mid \text{per a tot prefix $u$ de $w$} \ \ |u|_(\geq |u|_)\land |w|_(=|w|_)\}.

De manera semblant, sigui \mathsf{dyck}(s) el llenguatge de Dyck sobre s parells de parèntesis, és a dir, el llenguatge de les seqüències equilibrades de s tipus diferents de parèntesis. Per exemple, donats els dos tipus de parèntesis (, ), i [, ], es compleix que ([])\in \mathsf{dyck}(2) i ()[]\in \mathsf{dyck}(2) però ([)]\notin \mathsf{dyck}(2).

1. Demostreu que la gramàtica S \to SS \mid (S) \mid \lambda genera exactament \mathsf{dyck}(1). És ambigua?

2. Demostreu que la gramàtica S \to (S)S \mid \lambda genera exactament \mathsf{dyck}(1). És ambigua?

3. Demostreu que la gramàtica S \to SS \mid (S) \mid [S] \mid\lambda genera exactament \mathsf{dyck}(2). És ambigua?

4. Demostreu que la gramàtica S \to (S)S \mid [S]S \mid \lambda genera exactament \mathsf{dyck}(2). És ambigua?

5. Construïu una gramàtica inambigua que generi \mathsf{dyck}(s) per a un s arbitrari.

6. Sigui \Sigma=\{(,),[,]\} i L el llenguatge de tots els mots sobre \Sigma^* que, ignorant els símbols [, ], estan ben parentitzats sobre (, ), i, similarment, ignorant els símbols (, ), estan ben parentitzats sobre [, ]. En particular, \mathsf{dyck}(2)\subseteq L, però la inclusió és estricta. Per exemple, ([)]\in L\setminus \mathsf{dyck}(2). Demostreu que L no és un llenguatge incontextual.

   Consell

   Feu servir el fet que el llenguatge \{a^nb^nc^n \mid n\in \mathbb N\} no és incontextual.

Nota

Els llenguatges de Dyck són importants perquè, en cert sentit, són els llenguatges incontextuals més difícils. En efecte, el teorema de representació Chomsky–Schützenberger estableix que un llenguatge L és incontextual si i només si L és la imatge per homomorfisme de la intersecció d’algun \mathsf{dyck}(s) amb un llenguatge regular.

Exercici 4 (Operacions de tancament dels incontextuals i ambigüitat) Donades dues gramàtiques incontextuals inambigües G_1 i G_2,

1. podria ser que la construcció per obtenir la unió G_1\cup G_2 donés com a resultat una gramàtica ambigua?
2. podria ser que la construcció per obtenir la concatenació G_1\cdot G_2 donés com a resultat una gramàtica ambigua?
3. podria ser que la construcció per obtenir l’estrella de Kleene G_1^* donés com a resultat una gramàtica ambigua?
4. podria ser que la construcció per obtenir el revessat G_1^R donés com a resultat una gramàtica ambigua?
5. donat també un homomorfisme \sigma, podria ser que la construcció per obtenir \sigma(G_1) donés com a resultat una gramàtica ambigua?

Exercici 5 (Depuració de gramàtiques)  

1. Donada una gramàtica G, descriviu un algorisme per eliminar les \lambda-produccions (amb només una excepció possible) de G (sense canviar el llenguatge generat). Assegureu-vos que quan G és inambigua, l’algorisme descrit dona una gramàtica inambigua. Quin és el cost de l’algorisme?

2. Donada una gramàtica G, descriviu un algorisme per eliminar les produccions unàries de G (sense canviar el llenguatge generat). Assegureu-vos que quan G és inambigua, l’algorisme descrit dona una gramàtica inambigua. Quin és el cost de l’algorisme?

3. Donada una gramàtica G, descriviu un algorisme per eliminar els símbols inútils de G (sense canviar el llenguatge generat). Assegureu-vos que quan G és inambigua, l’algorisme descrit dona una gramàtica inambigua. Quin és el cost de l’algorisme?

4. Apliqueu l’algorisme de depuració (eliminació de \lambda-produccions, produccions unàries, símbols no fecunds i inaccessibles) a les gramàtiques següents:

   1. \left\{\begin{array}{ccl} S &\to& SS \mid (S) \mid \lambda \end{array}\right.
   2. \left\{\begin{array}{ccl} S &\to& (S)S \mid \lambda \end{array}\right.
   3. \left\{\begin{array}{ccl} S &\to& AA \\ A &\to& AA\mid \lambda \end{array}\right.
   4. \left\{\begin{array}{ccl} S &\to& A \\ A &\to& B \\ B &\to& c \end{array}\right.
   5. \left\{\begin{array}{ccl} S &\to& AB \\ A &\to& a\mid \lambda \\ B &\to& b\mid \lambda \end{array}\right.
   6. \left\{\begin{array}{ccl} S &\to& AB \\ A &\to& aAb\mid \lambda \\ B &\to& bBc\mid \lambda \end{array}\right.
   7. \left\{\begin{array}{ccl} S &\to& BC \mid \lambda \\ A &\to& aA\mid \lambda \\ B &\to& bB \\ C &\to& c \end{array}\right.
   8. \left\{\begin{array}{ccl} S &\to& X\mid Y \lambda \\ X &\to& Xc\mid A \\ A &\to& aAb\mid \lambda \\ Y &\to& aY \mid B \\ B &\to& bBc \mid \lambda \end{array}\right.
   9. \left\{\begin{array}{ccl} S &\to& A\mid B \mid C \\ A &\to& SaSbS \mid \lambda \\ B &\to& SbSaS \mid \lambda \\ C &\to& Cc\mid \lambda \end{array}\right.

Exercici 6 (Sobre la forma normal de Chomsky)  

1. Donada una gramàtica incontextual G, descriviu un procediment de temps polinòmic per construir una gramàtica G' que generi el mateix llenguatge que G i que estigui en forma normal de Chomsky.

2. Donada una gramàtica G en forma normal de Chomsky i un mot w generat per G, en quantes passes es produeix w? (en funció de |w|)

Nota

Recordeu que una gramàtica incontextual G està en forma normal de Chomsky si totes les seves produccions són de la forma:

\begin{aligned} A &\to BC, \text{o} \\ A &\to a, \text{o} \\ S &\to \lambda, \end{aligned} on A, B i C són símbols no terminals, a és un símbol terminal i S és el símbol inicial. A més, ni B ni C poden començar pel símbol S i la producció S\to \lambda només pot aparèixer si \lambda és al llenguatge generat per G.

Exercici 7 (La pertinença a un incontextual és decidible en temps polinòmic) Considereu el problema decisional següent:

\mathtt{Pertinen\c{c}a_{CFL}}: \text{ donada una entrada $x\in \{0,1\}^*$ i una CFG $G$, determinar si } x\in L(G).

Demostreu que \mathtt{Pertinen\c{c}a_{CFL}} es pot decidir en temps polinòmic respecte de |x| i la mida de G. Feu-ho explicant com funciona l’algorisme Cocke-Kasami-Younger (CKY).

Precaució

L’algorisme CKY assumeix que l’entrada és una gramàtica en forma normal de Chomsky.

Exercici 8 (Propietats decidibles dels incontextuals) Sigui L_G un llenguatge (incontextual) generat per una gramàtica incontextual G. Donada la gramàtica G com a entrada, descriviu un algorisme que decideixi si

1. L_G és buit.
2. L_G és infinit.
3. L_G conté algun mot de mida parella.
4. L_G conté infinits mots de mida parella.

Quin és el cost asimptòtic de l’algorisme proposat com a funció del nombre de símbols de G?

Important

Més endavant en el curs veurem que per a tot un seguit de preguntes molt naturals sobre gramàtiques incontextuals no existeix cap algorisme que les decideixi. No és que encara no se n’hagi trobat un algorisme. No existeix cap algorisme que sempre acabi i retorni la resposta. Per exemple:

• Donada una gramàtica incontextual, és ambigua?
• Donada una gramàtica incontextual, descriu un llenguatge regular?
• Donada una gramàtica incontextual G amb terminals \{a,b\}, és L_G=\{a,b\}^*?
• Donades dues gramàtiques incontextuals G_1 i G_2, és L_{G_1}\cap L_{G_2} buit?
• Donades dues gramàtiques incontextuals G_1 i G_2, és L_{G_1}= L_{G_2}?
• Donades dues gramàtiques incontextuals G_1 i G_2, és L_{G_1}\subseteq L_{G_2}?

Exercici 9 (El complementari d’un incontextual pot ser incontextual) En general, els llenguatges incontextuals no són tancats per complementació, és a dir, donat un llenguatge incontextual L, no és cert en general que \overline L també sigui incontextual.

Aquest exercici tracta sobre incontextuals el complementari dels quals resulta ser també incontextual.

1. Doneu una gramàtica incontextual inambigua que generi L=\{a^nb^n \mid n\in \mathbb N\} i una gramàtica incontextual que generi \overline L. Podeu fer que la segona sigui inambigua?

   Consell

   Feu servir RACSO per comprovar si la gramàtica que heu proposat per a \overline L és inambigua.

2. Doneu una gramàtica incontextual inambigua que generi L=\{w\in \{a,b\}^* \mid w=w^R\} i una gramàtica incontextual que generi \overline L. Podeu fer que la segona sigui inambigua?

   Consell

   Feu servir RACSO per comprovar si la gramàtica que heu proposat per a \overline L és inambigua.

Exercici 10 (Condicions suficients per la inambigüitat) Considereu les condicions següents per a una gramàtica incontextual:

1. Cada producció té un màxim d’una variable a la part dreta.
2. Els llenguatges generats a partir de dues produccions diferents d’una variable sempre són disjunts.

Demostreu que tota gramàtica incontextual que satisfaci les condicions anteriors ha de ser inambigua.

Exercici 11 (Sobre les gramàtiques regulars) Una gramàtica incontextual G=(V,\Sigma,P,S) se’n diu lineal per la dreta si totes les seves produccions són de la forma A \to wB o A \to w, on A, B \in V i w \in \Sigma^*. En el cas en què totes les produccions de G són de la forma A \to Bw o A \to w, es diu que G és lineal per l’esquerra. Una gramàtica incontextual és regular si és lineal per la dreta o lineal per l’esquerra. Una gramàtica incontextual és lineal si conté produccions de la forma A \to wB, A \to Bw o A \to w.

1. Forma normal. Demostreu que per a tota gramàtica lineal per la dreta G=(V,\Sigma,P,S) existeix una gramàtica equivalent en què totes les produccions són de la forma A \to aB o A \to \lambda, on A, B \in V i a \in \Sigma. Observeu que es pot aplicar una transformació simètrica a les gramàtiques lineals per l’esquerra.

2. Gramàtiques lineals. Demostreu que una gramàtica lineal pot generar un llenguatge no regular.

3. Gramàtiques regulars. Demostreu que la classe de llenguatges generats per gramàtiques regulars coincideix amb la dels regulars.

   Consell

   Demostreu-ho només per les gramàtiques lineals per la dreta o per l’esquerra (es pot fer independentment per totes dues i són simètriques). Feu servir la forma normal del primer punt.

4. Inambigüitat dels regulars. Demostreu que tots els llenguatges regulars són inambigus.

   Consell

   Feu servir la construcció (del punt anterior) per transformar un autòmat determinista en una gramàtica regular i demostreu que la gramàtica obtinguda és inambigua.