
\documentclass[letterpaper,10pt]{article}

\hoffset=-3cm  
\voffset=-2.5cm
\textheight=24cm
\textwidth=17cm
\parindent=0cm
\parskip=0.2cm

%\usepackage[latin1]{inputenc}
\usepackage[spanish,activeacute]{babel}
\usepackage{amssymb}
\usepackage{amsfonts}
%\usepackage[leqno]{amsmath}
%\usepackage{amsthm}
%\usepackage{graphics}
\usepackage{epsfig}
%\usepackage{makeidx}
\usepackage{oz}
%\usepackage{mathpartir}
\usepackage{mathrsfs}
\usepackage{enumerate}
\usepackage[all]{xy}
%\usepackage{ulem}
%\usepackage[pdftex]{hyperref}

%\newcounter{chapter}
%\usepackage{infteo}

%\usepackage{zed-csp}
%\DeclareMathAlphabet{\mathpzc}{OT1}{pzc}{m}{it}

\date{2008-01-25}

\begin{document}
\begin{center}
\begin{tabular}{c}
\Large{Teor'ia de la Computaci'on 2}\\[2mm]
\Large{Soluci'on del Parcial 1}\\
\normalsize{25 de febrero de 2008} \hspace{1cm}
 Prof: \textsf{Rodrigo L'opez}\\
\end{tabular}
\end{center}


\begin{enumerate}
 \item \textbf{\textsf{[Punto de recuperaci'on del quiz]}}
 Sean $G_1=(N_1,T_1,P_1,\Sigma_1)$ y $G_2=(N_2,T_2,P_3,\Sigma_2)$ dos gram'aticas tipo 2 (independientes
del contexto). Describa c'omo construir, a partir de $G_1$ y $G_2$, una gram'atica $G$, independiente del contexto,
tal que $L(G)=L(G_1)\uni L(G_2)$.

\textsf{Soluci'on:} Se define una nueva gram'atica $G=(N_1\cup N_2,T_1\cup T_2,P,\Sigma)$ que contiene:
\begin{itemize}
 \item Todos los s'imbolos
(terminales y no terminales) de las dos gram'aticas originales.
 \item Un nuevo s'imbolo distinguido $\Sigma$.
 \item Un nuevo conjunto de producciones $P= P_1\cup P_2\cup\{\Sigma\rightarrow\Sigma_1,\Sigma\rightarrow\Sigma_2\}$
\end{itemize}

Ahora, si $\omega\in L(G)$, su derivaci'on es de la forma $\Sigma\Rightarrow\Sigma_1\stackrel{*}{\Rightarrow}\omega$ 
(en cuyo caso tambi'en era derivable en $G_1$) o es de la forma $\Sigma\Rightarrow\Sigma_2\stackrel{*}{\Rightarrow}\omega$ 
(en cuyo caso tambi'en era derivable en $G_2$)
 \item Marque la opci'on correcta. Si $G$ es una gram'atica tipo 2 y ambigua entonces existe una cadena
  $\alpha \in L(G)$ para la cual:

% use packages: array
\begin{tabular}{ll}
$\bigcirc$ & Hay exactamente una derivaci'on por la derecha y exactamente una derivaci'on por la izquierda.\\[2mm] 
$\bigcirc$ & No hay derivaciones por la izquierda pero hay 2 o m'as derivaciones por la derecha. \\ [2mm]
$\bigcirc$ & No hay derivaciones por la derecha pero hay 2 o m'as derivaciones por la izquierda. \\ [2mm]
$\bigotimes$ & Hay m'as de una derivaci'on por la izquierda.\\[2mm]
$\bigcirc$ & Hay exactamente dos derivaciones por la izquierda y exactamente dos derivaciones por la derecha. \\ [2mm]
\end{tabular}

 \item Considere el Aceptador de Estados Finitos (no determin'istico) $M$ y la expresi'on regular $\alpha$ de la figura
siguiente. 

\begin{center}
 \epsfig{file=./imagenes/maquina1.eps} \hspace{2cm}$\alpha = (a\uni b)^*b(a\uni b)^*$
\end{center}

Llamaremos $L_{\alpha}$ al lenguaje definido por $\alpha$ y, como ha sido habitual, $L(M)$ ser'a el lenguaje aceptado por $M$.
\begin{enumerate}
 \item Calcule una expresi'on regular para el lenguaje $L_{\alpha}\inter L(M)$

\textsf{Soluci'on:} Se puede usar el siguiente m'etodo.
\begin{itemize}
 \item Construir un aceptador $M_{\alpha}$ para el lenguaje $L_{\alpha}$.
 \item Apoyarse en el anterior y en $M$ para construir un aceptador $M'$ para el lenguaje $L_{\alpha}\inter L(M)$.
 \item Calcular la expresi'on regular correspondiente.
\end{itemize}

\begin{center}
  \epsfig{file=./imagenes/interseccion.eps}
\end{center}

Se podr'ian plantear las ecuaciones simult'aneas de conjuntos para calcular la expresi'on regular correspondiente a $L(M')$ pero
es posible deducirla por simple inspecci'on. En efecto, en $M'$ solamente hay dos ``recorridos'' que conducen del estado inicial al final. Al primero corresponde la expresi'on $aa^*b(a\cup b)^*$ y al segundo corresponde la expresi'on $bb^*a(a\cup b)^*$. Es decir,
\begin{center}
\fbox{$L(M')=L_{\alpha}\inter L(M)=aa^*b(a\cup b)^*\cup bb^*a(a\cup b)^* = (aa^*b\cup bb^*a)(a\cup b)^*$}
\end{center}


 \item Calcule una expresi'on regular para el lenguaje 
       $L_{\alpha} - L(M)= \{\omega\in(a\uni b)^*\cbar\omega\in L_{\alpha} \mbox{\,\,y\,\,} \omega \notin L(M)\}$

  \textsf{Soluci'on:} El lenguaje pedido corresponde a $L_{\alpha} \cap L(M)^c$ luego se puede,
\begin{itemize}
 \item Calcular el aceptador para $L(M)^c$. Note que no basta con intercambiar estados finales por no finales
  porque $M$ es no determin'istico. La figura siguiente muestra la versi'on determin'istica de $M$ y luego el 
  aceptador $M^c$ que acepta el lenguaje $L(M)^c$.

\begin{center}
  \epsfig{file=./imagenes/complemento.eps}
\end{center}

  \item Calcular la ``intersecci'on'' de $M^c$ con $M_{\alpha}$. En la figura siguiente aparece la m'aquina calculada
  con el procedimiento est'andar de intersecci'on y al lado le versi'on reducida en la que se han eliminado (por simple
inspecci'on) los caminos que conducen a un estado de trampa.

\begin{center}
  \epsfig{file=./imagenes/interseccion2.eps}
\end{center}

  \item Calcular la expresi'on regular correspondiente al 'ultimo aceptador.
\begin{center}
 \fbox{$L_{\alpha} - L(M) = bb^*$}
\end{center}

\end{itemize}

\end{enumerate}

 \item Sea $R \subseteq V^*$ un conjunto regular sobre un alfabeto $V$ y sea $\alpha$ una cadena fija de $V^*$. Se
define \textit{la derivada de $R$ con respecto a} $\alpha$ como el conjunto $R_{\alpha}=\{\beta \cbar \alpha\beta\in R \}$.
Demuestre que $R_{\alpha}$ es regular. Ayuda: Describa c'omo, a partir de un aceptador para $R$, se puede construir un
aceptador para $R_{\alpha}$.

\textsf{Soluci'on:} Sea $M=(Q,V,f,F,q_I)$ un aceptador de estados finitos determin'istico tal que $R=L(M)$. Se estimula
a $M$ con la cadena $\alpha$ y se ve a qu'e estado se llega. Como $M$ es determin'istico ese estado es 'unico. Ahora definimos una
nueva m'aquina que usa ese estado como estado inicial. Las cadenas aceptadas a partir de ese estado son justamente las
$\beta$ tales que $\alpha \beta$ eran aceptadas por el aceptador original.

M'as formalmente, definimos $M_{\alpha}=(Q,V,f,F,q_{\alpha})$ en donde $q_I\stackrel{\alpha}{\Rightarrow}q_{\alpha}$.

 \item Describa un algoritmo que permita decidir si un lenguaje regular es finito o infinito (puede usar cualquiera
  de los algoritmos discutidos en clase).

\textsf{Soluci'on:} Si el lenguaje es regular debe existir un aceptador de estados finitos determin'istico $M=(Q,S,f,F,q_I)$ que
lo acepte. Suponga que hay $n$ estados en $Q$. El algoritmo propuesto es el siguiente:
\begin{enumerate}
 \item Construya el conjunto $J=\{\omega\in S^*\;\;\mbox{tales que}\;\;n\leq |\omega|<2n\}$.
 \item Estimule a $M$ con cada una de las cadenas de $J$ y ahora,
\begin{itemize}
\item  Si alguna cadena es aceptada entonces el lenguaje es infinito. 
\item Si ninguna cadena es aceptada entonces el lenguaje es finito.
\end{itemize}

\end{enumerate}

\textsf{Explicaci'on:} Si una cadena $\omega\in J$ es aceptada, en su sucesi'on admisible de estados tiene que haber un estado $q$
que se repite, de modo que debe ser posible escribir $\omega =\alpha\phi\psi\;\mbox{con}\;\phi\neq\lambda$ y en $M$
\begin{center}
 $q_I\stackrel{\alpha}{\Rightarrow}q\stackrel{\phi}{\Rightarrow}q\stackrel{\psi}{\Rightarrow}q'\in F$
\end{center}

Es decir, la cadena $\phi$ puede ser ``bombeada'' de manera que el conjunto de cadenas de la forma
 $\alpha\phi^*\psi$ 
tambi'en debe ser aceptado por $M$ y ese conjunto es infinito.

 \item Demuestre que el lenguaje $P=\{a^p \cbar p \mbox{ es primo}\}$ no es regular. Ayuda: recuerde que un entero $n$ \textsf{no es primo}
 cuando puede expresarse como el producto de dos enteros $n=q\times r$ y adem'as $q,r > 1$.

\textsf{Soluci'on:} Suponga que $P$ es regular. Es decir, existe un aceptador de estados finitos determin'istico $M=(Q,\{a\},f,F,q_I)$
tal que $P=L(M)$. Suponga adem'as que hay $n$ estados en $Q$. Como el conjunto de primos es infinito, siempre es posible escoger
un primo $p\geq n$. Si se estimula a $M$ con la cadena $a^p$, en la sucesi'on admisible de estados para $a^p$ tiene que haber un estado $q$
que se repite; es decir, debe ser posible escribir $a^p$ en la forma $a^sa^ta^u$ con $p=s+t+u,\,\,\,t\geq 1$ y adem'as, en $M$ 
\begin{center}
 $q_I\stackrel{a^s}{\Rightarrow}q\stackrel{a^t}{\Rightarrow}q\stackrel{a^u}{\Rightarrow}q'\in F$
\end{center}

Es decir, la subcadena $a^t$ puede ser ``bombeada'' para obtener otras cadenas aceptadas por $M$ y en consecuencia todo el conjunto 
\begin{center}
$X=\{a^s(a^t)^*a^u\;\cbar\;p=s+t+u,\,\,\,t\geq 1\}\subseteq L(M)$ 
\end{center}
tambi'en debe ser aceptado por $M$. En particular, $a^t$ podr'ia bombearse $s+u$ veces de modo que la longitud total de la cadena
ser'ia $s+t(s+u)+u=(s+u)(t+1)$ que evidentemente no es primo y la cadena correspondiente no podr'ia estar en $P$. Es decir,
P no puede ser regular.
\end{enumerate}


\end{document}
