Siguiente: Irresolubilidad de problemas en Un nivel arriba: Problema de la correspondencia Anterior: Presentación del Problema de

Una aplicación de PCP

Veremos aquí un problema típico relativo a gramáticas libres de contexto que es irresoluble, y cuya irresolubilidad se demuestra viendo que es equivalente al Problema de la Correspondencia de Post. Recordamos las siguientes definiciones

• Una palabra w en el lenguaje libre de contexto (LLC) L es ambigua en una GLC G que genere a L si w posee más de una derivación siniestra (leftmost) en G. Como un ejemplo trivial, se tiene que, en la gramática con producciones $S\rightarrow A\vert B$, $A\rightarrow a$, $B\rightarrow a$, la palabra a posee dos derivaciones siniestras
  
  $$\begin{array}{ccc} S\rightarrow A\rightarrow a &\ ;\ & S\rightarrow B\rightarrow a \end{array}$$
  
  

• Una GLC G es ambigua si hay una palabra, del lenguaje que genera, ambigua en ella.
• Un LLC L es inherentemente ambiguo si cualquier GLC G que lo genere es ambigua. A guisa de ejemplo se tiene que el lenguaje
  
  $$L=\{a^nb^nc^md^m\vert n,m\geq 1\}\cup\{a^nb^mc^md^n\vert n,m\geq 1\}=L_1\cup L_2.$$
  
  
  es inherentemente ambiguo. Sin que presentemos aquí una demostración formal de esta aseveración, daremos una motivaci''on intuitiva de ella. Seguramente el lector no tendrá ninguna dificultad en visualizar una GLC para generar L₁ y otra para generar L₂. Ahora, consideremos el lenguaje $L_0=\{a^nb^nc^nd^n\vert n\geq 1\}.$ Tenemos que $L_0\subset L_1\cap L_2\subset L$ y cada palabra en L₀ puede ser derivada tanto por la gramaática de L₁ como por la gramaática de L₂. Una y otra derivación hacen que cada papalabra de L₀ se a ambigua (para cualquier gramática de L).

El Problema de Reconocimiento de Ambigüedad en GLC (PRAGLC) es el siguiente:


Instancia:

Solución:

Proposición 2.2   PCP se reduce algorítmicamente a PRAGLC. Por tanto este último es irresoluble.

Demostración: Dada una instancia $(\mbox{\bf X},\mbox{\bf Y})$ de PCP hemos de construir una instancia $I_{\mbox{\it PRAGLC}}$ de PRAGLC, la cual consistirá de una gramática $G_{(\mbox{\scriptsize\bf X},\mbox{\scriptsize\bf Y})}$, de manera que $(\mbox{\bf X},\mbox{\bf Y})$ posea solución en PCP si y sólo si $G_{(\mbox{\scriptsize\bf X},\mbox{\scriptsize\bf Y})}$ sea ambigua. Denotemos por A al alfabeto de PCP. Escribamos $\mbox{\bf X} =\left[\mbox{\bf x}_1\cdots \mbox{\bf x}_k\right]$, $\mbox{\bf Y}=\left[\mbox{\bf y}_1\cdots \mbox{\bf y}_k\right]$, y extendamos A incluyendo k nuevos símbolos $b_1,\ldots,b_k$. Construyamos los siguientes dos lenguajes:

$$\begin{eqnarray*}L_{\mbox{\scriptsize\bf X}} &=& \left\{\mbox{\bf x}_{i_1}\cdots... ...cdots b_{i_1}\vert[i_1,\ldots,i_m]\in[1,k]^m,m\geq 1 \right\}. \end{eqnarray*}$$

Sea $G_{(\mbox{\scriptsize\bf X},\mbox{\scriptsize\bf Y})}=\left(\{S,S_{\mbox{\scriptsize\bf X}},S_{\mbox{\scriptsize\bf Y}}\},A\cup\{b_i\}_{i\leq k},P,S\right)$ la GLC cuyas producciones son:

$$\begin{eqnarray*}S &\rightarrow& S_{\mbox{\scriptsize\bf X}}\vert S_{\mbox{\scri... ...y}_{i}S_{\mbox{\scriptsize\bf Y}}b_i \vert \mbox{\bf y}_{i}b_i \end{eqnarray*}$$

Resultan evidentes las propiedades siguientes:

• El lenguaje generado por esta gramática es $L(G_{(\mbox{\scriptsize\bf X},\mbox{\scriptsize\bf Y})})=L_{\mbox{\scriptsize\bf X}} \cup L_{\mbox{\scriptsize\bf Y}} .$
• $G_{(\mbox{\scriptsize\bf X},\mbox{\scriptsize\bf Y})}$ es ambigua si y sólo si se cumple cualquiera de las siguientes dos proposiciones claramente equivalentes entre sí:

  1.

  $L_{\mbox{\scriptsize\bf X}}\cap L_{\mbox{\scriptsize\bf Y}}\not=\emptyset$

  2.

  $(\mbox{\bf X},\mbox{\bf Y})$ posee solución en PCP.

Siguiente: Irresolubilidad de problemas en Un nivel arriba: Problema de la correspondencia Anterior: Presentación del Problema de