\documentclass[11pt]{report}

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

\newcounter{conta}

\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 Primeira Lista de Exercícios} \hfill Data de entrega: 17/4/2018 \hfill Valor: 10 pontos

\vspace*{3mm}
\begin{enumerate}
 \item Uma versão do \emph{problema da parada}, problema este a ser abordado no Capítulo 5, é: dado um programa (sem
       entrada), determinar se ele para. Lá no Capítulo 5 será visto que não existe algoritmo que, recebendo como
			 entrada um (texto de) programa qualquer em C (ou em outra linguagem de programação), determine se ele para ou
			 não. Em outras palavras, o problema da parada não é decidível (computável). Sabendo disto, argumente que o problema
			 ``\emph{dado um programa qualquer em C, determinar se ele atribui o valor 0 à variável inteira X}'', também não é
			 computável.
 \item Seja $\Sigma$ o conjunto das 26 letras minúsculas do alfabeto português. Seja $n\in\mathbb{N}$.
       \begin{list}{\bf\alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \item Quantas palavras há na linguagem $\Sigma^n$?
        \item Quantas palavras há na linguagem $(\Sigma\cup\{\lambda\})^n$?
        \item Quantas palavras de $\Sigma^n$ contêm a letra $a$ e não contêm letras repetidas?
        \item Quantas palavras de $\Sigma^n$ contêm a letra $a$?
       \end{list}
 \item Sejam $A=\{\tt{00},{\tt 11}\}$, $B=\{\tt{01},{\tt 10}\}$ e $C=\{\lambda,{\tt 1}\}$. Calcule:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \item $AA$;
        \item $AC$;
        \item $CC$;
        \item $ABC$;
        \item $A(B\cup C)$;
        \item $AB\cup AC$.
       \end{list}
 \item Encontre linguagens $A$, $B$ e $C$ tais que $A(B-C)\not=AB-BC$.
 \item Seja $\Sigma$ o conjunto de todas as 26 letras do alfabeto e $C$ o conjunto das 21 consoantes. Seja $D$ o conjunto
       de todas as palavras de um dicionário da lingua portuguesa. A partir desses conjuntos, usando operações sobre
			 conjuntos, concatenações e fechos de Kleene, descreva o conjunto das palavras do dicionário que:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
			  \item contêm pelo menos uma das letras A, B ou C;
			  \item contêm as letras A e B, mas não C;
			  \item não contêm A nem B;
			  \item começam com a letra A;
			  \item começam com a letra A e contêm pelo menos uma consoante;
			  \item contêm a subpalavra RR.
			 \end{list}
 \item Sejam $A$, $B$ e $C$ linguagens sobre um alfabeto $\Sigma$. Mostre que:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \item $A(B\cup C)=(AB)\cup(AC)$;
        \item nem sempre $A(B\cap C)=(AB)\cap(AC)$.
       \end{list}
 \item Seja a linguagem $X$, de alfabeto $\{{\tt a},{\tt b}\}$, definida assim:
       \begin{list}{\bf\alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \item $\lambda\in X$;
        \item se $x\in X$ então ${\tt a}x\in X$ e ${\tt a}x{\tt b}x\in X$;
        \item $x\in X$ somente se pode ser obtido como especificado em (a) e (b).
       \end{list}
       Sejam $n_{\tt a}(x)$ e $n_{\tt b}(x)$ o numero de {\tt a}s e de {\tt b}s, respectivamente, na palavra $x$. Prove,
			 por indução, que $n_{\tt a}(x) \geq n_{\tt b}(x)$.
 \item Seja a gramática $(\{A,B\},\{{\tt 0},{\tt 1}\},R,A)$, em que $R$ tem as três regras:
         \begin{enumerate}
          \item[\ \ \ ] $A\rightarrow B B$
          \item[\ \ \ ] $B\rightarrow {\tt 0} B {\tt 1} \,|\, \lambda$
         \end{enumerate}
         Dê todas as derivações das seguintes palavras:
         \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
          \item $\lambda$;
          \item {\tt 01};
          \item {\tt 0101};
          \item {\tt 0011}.
         \end{list}
         Que linguagem é gerada?
 \item Construa gramáticas para as seguintes linguagens:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
			  \item $\{{\tt 0}\}\{{\tt 0},{\tt 1}\}^*\{11\}$;
			  \item $\{\lambda,{\tt 0}\}\{{\tt 11}\}^*\{\lambda,{\tt 0}\}$;
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, \mbox{ o número de {\tt a}s em $w$ é par}\}$;
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w=w^R\}$.
       \end{list}
       Para as duas últimas, determine o número de passos para gerar uma palavra de $n$ símbolos.
 \item Diga que linguagens são geradas pelas gramáticas:
       \begin{list}{\bf\alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \item $G_1=(\{A\},\{{\tt 0},{\tt 1}\},R_1,A)$, sendo $R_1$ constituído de:
              \begin{quote}
			         $A\,\rightarrow\, {\tt 0} A \,|\, A{\tt 0} \,|\, {\tt 1}$
		      	  \end{quote}
        \item $G_2=(\{B\},\{{\tt 0},{\tt 1}\},R_2,B)$, sendo $R_2$ constituído de:
              \begin{quote}
			         $B\,\rightarrow\, {\tt 0}B{\tt 00} \,|\, {\tt 1}$
			        \end{quote}
        \item $G_3=(\{S,A,B\},\{{\tt 0},{\tt 1}\},R_3,S)$, sendo $R_3$ constituído de:
              \begin{quote}
			         $S\,\rightarrow\, AA \,|\, B$ \\
			         $A\,\rightarrow\, {\tt 0} A \,|\, A{\tt 0} \,|\, {\tt 1}$\\
			         $B\,\rightarrow\, {\tt 0}B{\tt 00} \,|\, {\tt 1}$
			        \end{quote}
       \end{list}

 \item Identifique as linguagens geradas pelas gramáticas:
       \begin{list}{\bf\alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \item $G_1=(\{P,X\},\{{\tt a},{\tt b}\},R_1,P)$.
              \begin{enumerate}
               \item[$R_1$:]  $P\,\rightarrow\,{\tt a} X \,|\, {\tt b} P \,|\, \lambda$
               \item[\ ]      $X\,\rightarrow\,{\tt a} P$
              \end{enumerate}

        \item $G_2=(\{P,A\},\{{\tt a},{\tt b}\},R_2,P)$.
              \begin{enumerate}
               \item[$R_2$:]  $P\,\rightarrow\,{\tt a}P{\tt a}\,|\, A$
               \item[\ ]      $A\,\rightarrow\,{\tt b}A \,|\, {\tt b}$
              \end{enumerate}

        \item $G_3=(\{A,B\},\{{\tt 0},{\tt 1}\},R_3,A)$.
              \begin{enumerate}
               \item[$R_3$:]  $A\,\rightarrow\,{\tt 0}A\,|\, B$
               \item[\ ]      $B\,\rightarrow\,B{\tt 1} \,|\, {\tt 01}$
              \end{enumerate}

        \item $G_4=(\{P,X\},\{{\tt a},{\tt b}\},R_4,P)$.
              \begin{enumerate}
               \item[$R_4$:]  $P\,\rightarrow\,{\tt a} P \,|\, X {\tt b} \,|\, \lambda$
               \item[\ ]      $X\,\rightarrow\,{\tt a} P$
              \end{enumerate}

        \item $G_5=(\{P,X\},\{{\tt a},{\tt b}\},R_5,P)$.
              \begin{enumerate}
               \item[$R_5$:]  $P\,\rightarrow\,{\tt aa} P \,|\, X {\tt b} \,|\, \lambda$
               \item[\ ]      $X\,\rightarrow\,{\tt a} P$
              \end{enumerate}
       \end{list}
 \item Sejam os PDs:
       \begin{list}{\bf\alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \item determinar se um número natural $n$, para $1\leq n\leq 200$, é um número primo;
        \item dada uma equação do segundo grau de coeficientes $a$, $b$ e $c$, determinar se suas raízes são ambas reais,
				      se cada um dos coeficientes é um número natural entre 10 e 20 (exclusive);
        \item dada uma equação do segundo grau de coeficientes $a$, $b$ e $c$, determinar se suas raízes são ambas reais,
				      se seus coeficientes podem ser números reais quaisquer;
        \item dada uma fórmula da lógica de predicados, determinar se ela é válida;
        \item dados dois conjuntos finitos, determinar se eles são disjuntos;
        \item determinar se uma árvore $A$ tem altura menor ou igual a $n$;
        \item determinar se uma palavra $w$ é palíndromo, se $w\in\{{\tt 0},{\tt 1}\}^*$.
       \end{list}
       Dizer quantos parâmetros e quantas instâncias tem cada um.

 \item Diz-se que um PD $P$ é \emph{redutível} a um PD $Q$, se existe um algoritmo $\mathcal{R}$ que, recebendo $x$ como entrada,
       produz um resultado $y$ tal que a resposta a $P$ para a entrada $x$ é idêntica ou complementar\footnote{\noindent \ A
			 resposta complementar a \emph{sim} é \emph{não}, e a \emph{não} é \emph{sim}.} à resposta a $Q$ para a entrada $y$,
			 qualquer que seja a entrada $x$. Diz-se, com isso, que o algoritmo $\mathcal{R}$ pode ser usado para \emph{reduzir} o
			 problema $P$ ao problema $Q$.

       Seja $D$ um PD decidível e $I$ um PD indecidível. O que se pode dizer de um PD $X$, com relação à sua decidibilidade, se:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \item $D$ é redutível a $X$?
        \item $X$ é redutível a $D$?
        \item $I$ é redutível a $X$?
        \item $X$ é redutível a $I$?
       \end{list}
 \item \label{emcs}
         Faça um diagrama de estados, similar àquele do quebra-cabeça LCR, para o problema dos missionários 
				 e canibais:
         \begin{quote}
           Três missionários e três canibais devem atravessar um rio. Para isso, dispõem de uma canoa que pode transportar
					 no máximo duas pessoas de cada vez. Durante a travessia, se o número de canibais for maior que o de missionários
					 em qualquer uma das margens, os canibais comem os missionários. Determinar um plano para travessia em que nenhum
					 missionário seja devorado.
         \end{quote}
 \item Faça um diagrama de estados, usando a ideia apresentada na Seção 2.1.2, para uma máquina que determine se uma 
       sequência ternária (com dígitos 0, 1 e 2) é divisível por 4.
 \item Construa AFDs que reconheçam:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \item $\{\lambda,{\tt 0}\}^2$;
        \item $\{\lambda,{\tt 0},{\tt 1}\}^2\{{\tt 1}\}^*$;
        \item $\{{011},{1}\}^*$.
        \item $\{{\tt 0},{\tt 1}\}^*-\{{\tt 0},{\tt 1},{\tt 00},{\tt 11}\}$;
        \item $\{{\tt 01}\}^*\{{\tt 10}\}^*$;
        \item $\{{00},{1}\}^*\{{0},{11}\}^*$.
       \end{list}

 \item Faça AFDs que reconheçam as linguagens:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \item $\{{\tt a}^m{\tt b}^n\,|\, m+n\geq 2\}$;
        \item $\{{\tt a}^m{\tt b}^n\,|\, m+n \mbox{ é par}\}$;
        \item $\{{\tt a}^m{\tt b}^n\,|\, m+n \mbox{ mod } 3 = 0\}$;
        \item $\{{\tt a}^n{\tt b}^n\,|\, n \leq 3\}$.
        \item $\{{\tt a}^m{\tt b}^n\,|\, m\leq 2 \mbox{ e } n \geq m+2\}$.
       \end{list}
 \item Dado um AFD $M$ e um conjunto $X$ de estados de erro em $M$, apresente em detalhes como seria um AFD $M'$,
			 equivalente a $M$, obtido pela substituição de todos os estados de $X$ em $M$ por um único estado de erro.
 \item Seja o AFD com o seguinte diagrama de estados:
       \begin{center}
        \mbox{\setlength{\unitlength}{1mm}
         \begin{picture}(100,40)
          \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

          \node[Nmarks=i](1)(10,20){1}
          \node(2)(30,30){2}
          \node(3)(30,10){3}
          \node[Nmarks=r](4)(50,30){4}
          \node(5)(50,10){5}
          \node[Nmarks=r](6)(70,30){6}
          \node(7)(70,10){7}
          \node(8)(90,20){8}

          \drawedge[curvedepth=2](1,2){{\tt 0}}
          \drawedge[curvedepth=0, ELside=r](1,3){{\tt 1}}
          \drawedge[curvedepth=2](2,1){{\tt 0}}
          \drawedge[curvedepth=0](2,3){{\tt 1}}
          \drawedge[curvedepth=0, ELside=r](3,4){{\tt 0}}
          \drawloop[loopangle=270](3){{\tt 1}}
          \drawedge[curvedepth=0](4,5){{\tt 0}}
          \drawedge[curvedepth=0](4,6){{\tt 1}}
          \drawloop[loopangle=270](5){{\tt 0}}
          \drawedge[curvedepth=2](5,7){{\tt 1}}
          \drawedge[curvedepth=0](6,7){{\tt 0}}
          \drawloop[loopangle=90](6){{\tt 1}}
          \drawedge[curvedepth=2](7,5){{\tt 0}}
          \drawloop[loopangle=270](7){{\tt 1}}
          \drawedge[curvedepth=0, ELside=r](8,6){{\tt 0}}
          \drawedge[curvedepth=0](8,7){{\tt 1}}
         \end{picture}
        }
       \end{center}
      \begin{list}{\bf\alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
       \item Obtenha o diagrama de estados de um AFD mínimo equivalente.
       \item Que linguagem é reconhecida pelo AFD em questão?
      \end{list}
\item Utilizando produto de autômatos, determine AFDs que re\-co\-nhe\-çam
         \begin{list}{\bf \alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
          \item a união e
          \item a interseção
         \end{list}
         das linguagens $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, n_{\tt 1}(w)\mbox{ mod } 3\not=0\}$ e
					              $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,|w| \mbox{ mod } 3=0\}$.
 \item Sejam
       \begin{itemize}\setlength{\parsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item $L_1=\{{\tt 0},{\tt 1}\}^*\{{\tt 1}\}\{{\tt 0},{\tt 1}\}^*$;
        \item $L_2=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ não contém }{\tt 00}\}$.
       \end{itemize}
       Construa autômatos finitos determinísticos que reconheçam:
       \begin{list}{\bf\alph{conta})}{\usecounter{conta}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}}
        \item $L_1$.
        \item $L_2$.
        \item $L_1-L_2$. Para isto, faça o produto dos autômatos que reconhecem $L_1$ e $\overline{L_2}$.
       \end{list}
 \item Construa AFNs para as seguintes linguagens sobre $\{{\tt a},{\tt b},{\tt c}\}$:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item o conjunto das palavras com, no mínimo, três ocorrências de {\tt abc};
        \item o conjunto das palavras com, no mínimo, três ocor\-rên\-cias de {\tt a}s ou três ocor\-rên\-cias de {\tt b}s ou
				      três de {\tt c}s;
        \item o conjunto das palavras com sufixo {\tt abc} ou {\tt bca};
        \item o conjunto das palavras em que existem duas ocorrências de {\tt abc} com um número ímpar de símbolos entre elas;
        \item o conjunto das palavras em que o último símbolo seja idêntico ao primeiro;
        \item o conjunto das palavras em que o último símbolo seja diferente do primeiro;
        \item o conjunto das palavras em que o último símbolo tenha ocorrido antes;
        \item o conjunto das palavras em que o último símbolo tenha ocorrido antes no máximo uma vez;
        \item o conjunto das palavras em que o último símbolo não tenha ocorrido antes;
        \item o conjunto das palavras com um único {\tt a} ou um único {\tt b} ou um único {\tt c}. 
      \end{list}
 \item Mostre que toda linguagem regular que não contenha a palavra $\lambda$ pode ser reconhecida por
       AFN que tenha apenas um estado inicial \textbf{e} um estado final.
 \item \label{edeafnpafd} Sejam os AFNs com os diagramas de estados da Figura~\ref{fdeafnpafd}.
       \begin{figure}[t]
       \begin{center}
       \begin{picture}(65,45)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}

        \put(30,0){\makebox(0,0){\textbf{(a) AFN 1.}}}
        \node[Nmarks=i, iangle=180](1)(10,25){1}
        \node(2)(25,35){2}
        \node(3)(25,15){3}
        \node[Nmarks=r](4)(40,25){4}
        \node[Nmarks=i, iangle=0](5)(55,25){5}

        \drawedge(1,2){\tt 0}
        \drawedge(1,3){\tt 1}
        \drawloop[loopangle=90](2){{\tt 0},{\tt 1}}
        \drawedge(2,4){\tt 1}
        \drawloop[loopangle=270](3){{\tt 0},{\tt 1}}
        \drawedge(3,4){\tt 0}
        \drawedge(5,4){\tt 0}
       \end{picture}
       \begin{picture}(65,45)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}

        \put(30,0){\makebox(0,0){\textbf{(b) AFN 2.}}}
        \node[Nmarks=i, iangle=180](1)(10,25){1}
        \node(2)(25,35){2}
        \node[Nmarks=i, iangle=225](3)(25,15){3}
        \node[Nmarks=ir, iangle=0](4)(40,25){4}

        \drawloop[loopangle=90](1){{\tt 0},{\tt 1}}
        \drawedge(1,2){\tt 0}
        \drawedge(1,3){\tt 1}
        \drawedge(2,4){\tt 1}
        \drawedge(3,4){{\tt 0},{\tt 1}}
       \end{picture}
       \begin{picture}(65,50)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}

        \put(30,0){\makebox(0,0){\textbf{(c) AFN 3.}}}
        \node[Nmarks=i, iangle=180](1)(10,35){1}
        \node(2)(25,35){2}
        \node[Nmarks=i, iangle=180](3)(25,15){3}
        \node[Nmarks=i, iangle=70](4)(40,25){4}
        \node[Nmarks=ir, iangle=0](5)(55,25){5}

        \drawedge(1,2){${\tt 1}$}
        \drawloop[loopangle=90](2){{\tt 0},{\tt 1}}
        \drawedge(2,4){${\tt 1}$}
        \drawedge[ELside=r](3,4){${\tt 0},{\tt 1}$}
        \drawedge(4,5){${\tt 0},{\tt 1}$}
       \end{picture}
       \begin{picture}(65,50)
        \gasset{Nw=6, Nh=6, Nmr=3, fillcolor=Gray, fillgray=0.9, loopdiam=4}
        \node[Nmarks=i, iangle=180](1)(10,35){1}
        \node[Nmarks=i, iangle=180](2)(10,15){2}
        \node(3)(25,25){3}
        \node[Nmarks=r](4)(40,25){4}

        \put(30,0){\makebox(0,0){\textbf{(d) AFN 4.}}}
        \drawedge[curvedepth=0](1,3){{\tt a}}
        \drawedge[curvedepth=0, ELside=r](2,3){{\tt a}}
        \drawedge[curvedepth=0](3,4){{\tt b},{\tt c}}
        \drawloop[loopangle=90](1){{\tt a},{\tt b}}
        \drawloop[loopangle=270](2){{\tt a},{\tt c}}
       \end{picture}
       \end{center}

        \caption{\label{fdeafnpafd} AFNs para Exercício \ref{edeafnpafd}.}
       \end{figure}
       Obtenha AFDs equivalentes aos AFNs utilizando o método de construção de subconjuntos.
 \item Construa um AFN de 3 estados que reconheça $\{{\tt a}\}^*\{{\tt b}\}\cup\{{\tt b}\}^*\{{\tt a}\}$. Em seguida,
       obtenha um AFD equivalente pelo método da construção de subconjuntos.
 \item Sejam $L_1=\{1,01\}^+$ e $L_2=\{0,10\}^*$.
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item Construa AFNs (AFDs sem estados de erro) que reconheçam $L_1$ e $L_2$.
				\item Obtenha um AFN$\lambda$ que reconheça $L_1L_2$ usando transição $\lambda$, como exemplificado
			        no Exemplo 37 da Seção 2.3.
				\item Obtenha um AFN equivalente usando a técnica para eliminação de transições $\lambda$.
				\item Obtenha um AFD equivalente pelo método da construção de subconjuntos.
       \end{list}
 \item Espelhando-se nos Exemplos 37 a 40 da Seção 2.3 construa, a partir de AFN$\lambda$s, AFDs que reconheçam:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
				\item $\{{\tt a}\}\{\lambda,{\tt a},{\tt b}\}^2\{{\tt b}\}$;
        \item $\{{\tt a}\}^*(\{{\tt b}\}^*\cup\{{\tt c}\}^*)\{{\tt a}\}^*$;
        \item $\{{\tt aa}\}^*\{{\tt bb}\}^*\{{\tt cc}\}^*$.
       \end{list}

\end{enumerate}
\end{document}