\documentclass[12pt,a4paper]{report}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 

\usepackage{fullpage}
\usepackage{latexsym}
\usepackage{gastex}
\usepackage[usenames]{color}

\newcounter{conta}
\pagestyle{empty}
\begin{document}
 
\noindent Pós-Graduação em Ciência da Computação \hfill DCC/ICEx/UFMG \\
\noindent {\it Teoria de Linguagens} \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2014 \\
\noindent Professor: Newton José Vieira \\
\noindent {\it Prova Suplementar}/Solução do professor

\vspace*{3mm}
\begin{enumerate}
 \item {\footnotesize Apresente um diagrama de estados de um AFD que reconheça $(000+1)^*(00+11)$.}

       \textit{Solução}:

       \mbox{\setlength{\unitlength}{1mm}
        \begin{picture}(70,35)
         \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

         \node[Nmarks=i](1)(30,20){1}
         \node(2)(24,8){2}
         \node(3)(36,8){3}
         \node(4)(45,25){4}
         \node(5)(45,15){5}
         \node[Nmarks=r](6)(60,20){6}

         \put(5,20){\textbf{AFN:}}
         \drawloop[loopangle=90](1){\tt 1}
         \drawedge[curvedepth=0, ELside=r](1,2){\tt 0}
         \drawedge[curvedepth=0](1,4){\tt 0}
         \drawedge[curvedepth=0](1,5){\tt 1}
         \drawedge[curvedepth=0, ELside=r](2,3){\tt 0}
         \drawedge[curvedepth=0, ELside=r](3,1){\tt 0}
         \drawedge[curvedepth=0](4,6){\tt 0}
         \drawedge[curvedepth=0](5,6){\tt 1}
        \end{picture}
        \begin{picture}(70,35)
         \gasset{Nw=8, Nh=6, Nmr=7, ELdist=0.5, loopdiam=5, fillgray=0.9}

         \node[Nmarks=i](1)(25,20){1}
         \node(24)(40,25){24}
         \node(15)(40,8){15}
         \node(36)(55,25){36}
         \node[Nmarks=r](156)(55,8){156}

         \put(0,20){\textbf{AFD:}}
         \drawedge[curvedepth=0, ELside=r](1,15){\tt 1}
         \drawedge[curvedepth=0](1,24){\tt 0}
         \drawedge[curvedepth=0](15,24){\tt 0}
         \drawedge[curvedepth=0, ELside=r](15,156){\tt 1}
         \drawedge[curvedepth=0, ELside=r](156,24){\tt 0}
         \drawedge[curvedepth=0](24,36){\tt 0}
         \drawedge[curvedepth=-10, ELside=r](36,1){\tt 0}
        \end{picture}
       } \\

 \item {\footnotesize Apresente um diagrama de estados de um AFN que reconheça a linguagem
       $$L=\{w\in \{{\tt 0},{\tt 1}\}^*\,|\, {\tt 001} \mbox{ não é sufixo de } w\}$$ e que tenha as
       seguintes características:
       \begin{itemize}
        \item tem um único estado final; e
        \item para cada $w\in L$ existe uma única computação de sucesso.
			 \end{itemize}}

       \textit{Solução}:

       \mbox{\setlength{\unitlength}{1mm}
        \begin{picture}(70,25)
         \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

         \node[Nmarks=ir](1)(30,10){}
         \node[Nmarks=r](2)(45,10){}
         \node[Nmarks=r](3)(60,10){}
         \node(4)(75,10){}

         \put(5,20){\textbf{AFD:}}
         \drawloop[loopangle=90](1){\tt 1}
         \drawedge[curvedepth=3](1,2){\tt 0}
         \drawedge[curvedepth=3](2,1){\tt 1}
         \drawedge[curvedepth=0](2,3){\tt 0}
         \drawloop[loopangle=90](3){\tt 0}
         \drawedge[curvedepth=0](3,4){\tt 1}
         \drawedge[curvedepth=-14, ELside=r](4,1){\tt 1}
         \drawedge[curvedepth=6](4,2){\tt 0}
        \end{picture}
       } \\

       \mbox{\setlength{\unitlength}{1mm}
        \begin{picture}(70,30)
         \gasset{Nw=6, Nh=6, Nmr=6, ELdist=0.5, loopdiam=5, fillgray=0.9}

         \node[Nmarks=i](1)(30,20){}
         \node(2)(45,20){}
         \node(3)(60,20){}
         \node(4)(75,20){}
         \node[Nmarks=ri, iangle=210](f)(52.5,0){}

         \put(5,20){\textbf{AFN:}}
         \drawloop[loopangle=90](1){\tt 1}
         \drawedge[curvedepth=3](1,2){\tt 0}
         \drawedge[curvedepth=-5, ELside=r](1,f){{\tt 0},{\tt 1}}
         \drawedge[curvedepth=2](2,1){\tt 1}
         \drawedge[curvedepth=0](2,3){\tt 0}
         \drawedge[curvedepth=-2, ELside=r](2,f){{\tt 0},{\tt 1}}
         \drawloop[loopangle=90](3){\tt 0}
         \drawedge[curvedepth=0](3,4){\tt 1}
         \drawedge[curvedepth=3](3,f){\tt 0}
         \drawedge[curvedepth=-14, ELside=r](4,1){\tt 1}
         \drawedge[curvedepth=6, ELpos=40](4,2){\tt 0}
         \drawedge[curvedepth=5](4,f){{\tt 0},{\tt 1}}
        \end{picture}
       } \\

 \item {\footnotesize Se a linguagem $\{w\in\{{\tt a},{\tt b}\}^*\,|\, n_{\tt a}(w) \mbox{ é par e } n_{\tt b}(w) \mbox{ é primo}\}$ for 
       livre do contexto, prove que ela não é regular; caso contrário, prove que ela não é livre do contexto. ($n_{\tt a}(w)$
			 é o número de {\tt a}s em $w$.)}

       \textit{Solução}:

       Seja $L$ a linguagem em questão e suponha que $L$ seja LLC. Como a interseção de uma LLC com uma linguagem regular é
			 LLC, $L\cap\{{\tt b}\}^*$ é LLC. Mas $L\cap\{{\tt b}\}^*=\{{\tt b}^n\,|\, n \mbox{ é primo}\}$, e esta última não é LLC.
			 Contradição! Logo, $L$ não é LLC.

 \item {\footnotesize Seja $L=\{{\tt 0}^k{\tt 1}^n\,|\, k \mbox{ é ímpar e } k\not=n\}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Construa uma gramática livre do contexto que gere $L$.
        \item Para cada variável $X$ da gramática, dê $L(X)=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,X\stackrel{*}{\Rightarrow} w\}$.
	     \end{list}}

       \textit{Solução}:

       \begin{tabbing}
			  xxx\= xxxxxxxxxxxxxxxxxxxxxx\= \kill
				   \> $P \,\rightarrow\, X \,|\, Y$  \> $L(P)=L$ \\
				   \> $X \,\rightarrow\, {\tt 00}X \,|\, {\tt 0}A$  \> $L(X)=\{{\tt 00}\}^*\{{\tt 0}\}\{{\tt 11}\}^*$ \\
				   \> $A \,\rightarrow\, {\tt 11}A \,|\, \lambda$   \> $L(A)=\{{\tt 11}\}^*$ \\
				   \> $Y \,\rightarrow\, {\tt 00}Y{\tt 11} \,|\, {\tt 0}B{\tt 1} \,|\, {\tt 0}C{\tt 1}$ \>
					          $L(Y)=\{{\tt 0}^k{\tt 1}^n\,|\, k \mbox{ e } n \mbox{ ímpares e } k\not=n\}$ \\
				   \> $B \,\rightarrow\, {\tt 00}B \,|\, {\tt 00}$  \> $L(B)=\{{\tt 00}\}^+$ \\
				   \> $C \,\rightarrow\, {\tt 11}C \,|\, {\tt 11}$  \> $L(C)=\{{\tt 11}\}^+$ \\
			 \end{tabbing}

 \item {\footnotesize Mostre que é decidível ou que não é:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Dada uma GLC $G$, determinar se $L(G)\subseteq \{{\tt 1}\}^*$.
        \item Dada uma MT $M$ e um AFD $A$, determinar se $L(M)\subseteq L(A)$.
       \end{list}}

       \textit{Solução}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item É decidível. Elimine as variáveis inúteis de $G$; se \emph{nenhum terminal diferente de {\tt 1}} for referenciado
				      nas regras após a eliminação de variáveis inúteis, então $L(G)\subseteq \{{\tt 1}\}^*$; caso contrário,
							$L(G)\not\subseteq \{{\tt 1}\}^*$.
        \item É indecidível.  O problema de determinar se $L(M)\subseteq \emptyset$ é indecidível, pelo Teorema de Rice, visto
				      que ser subconjunto de $\emptyset$ é uma propridade não trivial de LREs.  E este problema pode ser reduzido ao
							problema em questão produzindo-se uma MT $M'=M$ e um AFD $A$ tal que $L(A)=\emptyset$. 
       \end{list}
\end{enumerate}

\end{document}
