
\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}\\[5mm]
\Large{Parcial 1}\\
\normalsize{25 de febrero de 2008}\\[5mm]
Alumno \rule{10cm}{.1mm} \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)$.
\vspace{2.5cm}

 \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]
$\bigcirc$ & 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)$
 \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)\}$
\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}$.

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

 \item Demuestre que el lenguaje $\{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$.
\end{enumerate}


\end{document}
