\documentclass[11pt]{report}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}
\usepackage{fullpage}
%\pagestyle{empty}
\usepackage{gastex}
\usepackage[usenames]{color}
\usepackage         {amsfonts}

\newcounter{conta}
\pagestyle{empty}

\begin{document}

\vspace*{1cm}
\noindent Departamento de Ciência da Computação \hfill ICEx/UFMG \\
\noindent {\it Teoria de Linguagens} \hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2018 \\
\noindent Professor: Newton José Vieira \\
\noindent {\bf Terceira Lista de Exercícios} \hfill Data de entrega: 10/7/2018 \hfill Valor: 10 pontos

\vspace*{3mm}
\begin{enumerate}
 \item Para cada linguagem a seguir, mostre que ela é ou não é LLC:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item $\{{\tt a}^n{\tt b}^i{\tt c}^j{\tt b}^k\,|\, n=k \mbox{ ou } i\not=j\}$;
        \item $\{{\tt a}^n{\tt b}^i{\tt c}^j{\tt b}^k\,|\, n=k \mbox{ ou } i=j=k\}$;
        \item $\{{\tt a},{\tt b},{\tt c}\}^*-\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\, n_{\tt a}(w)=n_{\tt b}(w)=n_{\tt c}(w)\}$.
       \end{list}
 \item Seja a MT $M=(\{1,2,3,4\},\{{\tt 0},{\tt 1}\},\{{\tt 0},{\tt 1},\langle,\sqcup\},\delta,1,\{1,2,3\})$ com o diagrama de estados:

       \mbox{\setlength{\unitlength}{1mm}
        \begin{picture}(120,35)
         \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

         \node[Nmarks=ir](1)(50,25){1}
         \node[Nmarks=r](2)(80,25){2}
         \node[Nmarks=r](3)(50,5){3}
         \node(4)(80,5){4}

         \drawedge[curvedepth=0](1,2){${\tt 0}/\sqcup$ {\sf E}}
         \drawloop[loopangle=0](2){\shortstack{$\langle/\langle$ {\sf D} \\
                                                 $\sqcup/\sqcup$ {\sf E}}}
         \drawedge[curvedepth=0](1,3){${\tt 1}/\sqcup$ {\sf D}}
         \drawloop[loopangle=180](3){${\tt 1}/\sqcup$ {\sf D}}
         \drawedge[curvedepth=0](3,4){$\sqcup/\sqcup$ {\sf E}}
        \end{picture}
       } \\

       Expresse a linguagem reconhecida por $M$ mediante uma expressão regular.
 \item Projete uma MT de três estados que reconheça $\{{\tt 1}^{3n}\,|\, n\geq 0\}$.
 \item Construa MTs que reconheçam \underline{por parada} as seguintes linguagens de alfabeto $\{{\tt 0},{\tt 1}\}$:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item $\{\lambda\}$;
        \item o conjunto das palavras que não contêm {\tt 00}.
      \end{list}
 \item Escreva MTs não determinísticas de duas fitas que reconheçam as linguagens:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,n_{\tt 1}(w)>n_{\tt 0}(w)\}$.
        \item $\{xy\,|\,x,y\in\{{\tt 0},{\tt 1}\}^*, |x|=|y| \mbox{ e } x\not=y^R\}$;
        \item $\{xy\,|\,x,y\in\{{\tt 0},{\tt 1}\}^*, |x|=|y| \mbox{ e } x\not=y\}$.
       \end{list}
       Procure obter MTs com o menor número de transições possível.
 \item Seja uma MT $M=(E,\Sigma,\Gamma,\delta,i,\{f\})$ cuja única diferença com relação a uma MT-padrão é que ela
       tem apenas um estado final. Suponha que a linguagem reconhecida por $M$ seja
       \[\{w\in\Sigma^*\,|\, [i,\langle\underline{w}]\stackrel{*}{\vdash} [f,x\underline{a}y]\}\mbox{.}\]
       Ou seja, para qualquer $w\in\Sigma^*$ $M$ reconhece $w$ se, e somente se, $M$ atinge o estado $f$ ao
			 processar $w$. Mostre que qualquer linguagem recursivamente enumerável pode ser
       reconhecida por uma MT desse tipo.
 \item Construa gramáticas irrestritas que gerem as linguagens:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item $\{{\tt 0}^n{\tt 1}^k{\tt 0}^n{\tt 1}^k\,|\, n,k\geq 0\}$;
        \item $\{{\tt a}^m{\tt b}^n{\tt c}^k\,|\, m\geq n\geq k\}$.
       \end{list}
 \item Construa GSCs para:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item $\{{\tt a}^m{\tt b}^n{\tt c}^k\,|\,m>n>k\}$;
        \item $\{wxw\,|\, w\in\{{\tt a},{\tt b}\}^* \mbox{ e } x\in\{{\tt c}\}^+ \}$.
       \end{list}
       Procure obter GSCs com um número mínimo de regras.
 \item Sejam duas linguagens $L_1$ e $L_2$. Considerando os (quatro) casos em que $L_1$ é LRE ou recursiva e $L_2$ é LRE ou recursiva, responda justificando:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item $L_1-L_2$ é necessariamente uma LRE?
        \item $L_1-L_2$ é necessariamente recursiva?
       \end{list}
 \item Seja $L$ uma linguagem \emph{não} recursivamente enumerável. Mostre que:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item Se $F$ é finita, $L-F$ não é recursivamente enumerável.
        \item Se $R$ é recursiva, $L-R$ pode ser recursiva ou não.
        \item $\overline{L}$ pode ser recursivamente enumerável.
       \end{list}
 \item Exiba as linguagens associadas ao PD ``determinar se $n$ é um número par menor do que 10'' para as duas representações
       apresentadas em exemplo da Seção 5.2.
 \item Mostre que a linguagem $\{R\langle M\rangle\,|\, L(M)\not=\emptyset\}$ é LRE.
 \item Seja a linguagem $\{R\langle M,w\rangle\,|\, \mbox{$M$ não para se a entrada for $w$}\}$. Prove que essa linguagem
			 não é recursivamente enumerável. Observe que essa linguagem é $\overline{L_{P}}$, excluídas as palavras que não
			 estejam na forma $R\langle M,w\rangle$.

 \item Mostre que se o problema da parada fosse decidível, então \mbox{toda LRE seria recursiva}.
 \item Para cada PD a seguir, mostre que o mesmo é indecidível:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item dados uma MT $M$, uma palavra $w$ e um estado $e$ de $M$, determinar se a computação de $M$ para a entrada
				      $w$ atinge o estado $e$;
        \item dados uma MT $M$ e um estado $e$ de $M$, determinar se a computação de $M$ para a entrada $\lambda$ atinge
				      o estado $e$;
        \item dada uma MT $M$, determinar se a computação de $M$ para a entrada $\lambda$ ``volta'' ao estado inicial de $M$;
        \item dados uma MT $M$ e um símbolo $a$ de $M$, determinar se a computação de $M$ para a entrada $\lambda$ escreve
				      $a$ na fita em algum momento;
        \item dados uma MT $M$ e uma expressão regular $r$, determinar se $L(M)\cap L(r)\not=\emptyset$.
       \end{list}
 \item Seja o problema: \emph{dada uma MT $M$, determinar se $x\in L(M)$, onde $x$ é uma palavra específica.}
       (Observe que \textbf{\textsl{o único parâmetro}} desse problema é $M$.)
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item Pode-se usar o Teorema de Rice para mostrar que esse problema é indecidível? Justifique.
        \item Reduza o problema da parada a este.
        \item A linguagem $L_x=\{R\langle M\rangle\,|\,x\in L(M)\}$ é LRE? Justifique.
       \end{list}
 \item Mostre que os seguintes problemas são decidíveis ou não:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
			  \item Dada uma MT $M$, determinar se ela é a única que reconhece $L(M)$;
			  \item Dadas uma MT $M$, determinar se $R\langle M\rangle \in L(M)$;
			  \item Dadas MTs $M_1$ e $M_2$, determinar se $\lambda\in L(M_1)\cup L(M_2)$;
			  \item Dada uma MT $M$, determinar se $L(M)=\{R\langle M\rangle\}$;
			  \item Dada uma MT $M$, determinar se ela para se recebe como entrada um palíndromo.
       \end{list}
 \item Mostre que é decidível ou que não é:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item Dados um conjunto finito $F$ e uma GLC $G$, determinar se $F\subseteq L(G)$;
        \item Dadas uma GR $R$ e uma GLC $G$, determinar se $L(G)\subseteq L(R)$;
        \item Dadas uma GR $R$ e uma GLC $G$, determinar se $L(R)\subseteq L(G)$;
        \item Dada uma GR $R$, determinar se $R$ é ambígua.
       \end{list}
 \item Mostre que são indecidíveis os problemas de se determinar, dadas duas GLCs $G_1$ e
       $G_2$, que:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item $L(G_1)=L(G_2)$;
        \item $L(G_1)\subseteq L(G_2)$.
       \end{list}


\end{enumerate}
\end{document}
