\documentclass[11pt,a4paper]{report}

\usepackage[brazil]{babel}
\usepackage[latin1] {inputenc}
\usepackage{fullpage}

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

\newcounter{conta}

\begin{document}
 
\noindent Pós-Graduação em Ciência da Computação  \hfill DCC/ICEx/UFMG \\
{\it Teoria de Linguagens}  \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2013 \\
Professor: Newton Jos\'{e} Vieira
 
\noindent {\bf Lista de Exercícios preparatória para a Primeira Prova}

\vspace*{3mm}
\noindent \textbf{Observação:}
\begin{itemize}
 \item O uso do software JFLAP, sugerido na página da disciplina, pode ser conveniente para solução de alguns
       exercícios.
\end{itemize}

\begin{enumerate}
 \item O seguinte texto foi tirado de um livro sobre análise combinatória:
       \begin{quote}
        \textbf{Segunda forma do princípio da indução matemática.}
        \textit{Seja $P(n)$ uma propriedade relativa aos inteiros. Se
        \begin{list}{(\roman{conta})}{\usecounter{conta}}
         \item $P(n)$ é verdadeira para $n=1$, e
         \item $P(n)$ verdadeira para $1<n\leq k$ implica que $P(k+1)$ é verdadeira,
        \end{list}
        então $P(n)$ é verdadeira para todo inteiro $n\geq 1$.}
       \end{quote}
       O que há de errado com isso (se é que há)?

 \item Seja $L=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,w$ não contém {\tt 11}$\}$.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Faça uma definição recursiva (tradicional) de $L$.
        \item Mostre que não existe linguagem $X$ tal que
              $L=X^*$. {\em Dica\/}: Suponha o contrário e considere a palavra ${\tt 1}\in L$.
       \end{list}

 \item \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Mostre que o conjunto $\{{\tt a}\}^*$ é enumerável. Para isto, construa uma função bijetora
				      $f:\{{\tt a}\}^* \rightarrow \mbox{\bf N}$.
        \item Mostre que o conjunto $F=\{C\subseteq\{{\tt a}\}^*\,|\, C \mbox{ é finito}\}$ é enumerável.
				      Para isto, construa uma função bijetora $g:F\rightarrow \mbox{\bf N}$.
        \item Mostre que o conjunto ${\cal P}(\{{\tt a}\}^*)$ não é enumerável.
       \end{list}

 \item Expresse as linguagens a seguir utilizando operações sobre conjuntos finitos de palavras de
       $\{{\tt 0},{\tt 1}\}^*$. Operações permitidas: união, interseção, diferença, concatenação e
	 		 fecho de Kleene, mas só use interseção ou diferença se não conseguir sem usar.
       O alfabeto é $\{{\tt 0},{\tt 1}\}$ para todas.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras que contêm {\tt 00} ou {\tt 11} ou ambas.
        \item O conjunto das palavras que contêm {\tt 00}, mas não {\tt 11}.
        \item O conjunto das palavras que contêm {\tt 00} ou {\tt 11}, mas não ambas.
        \item O conjunto das palavras que contêm {\tt 00} e {\tt 11}.
        \item O conjunto das palavras que não contêm {\tt 00}, nem {\tt 11}.
        \item O conjunto das palavras com número par de {\tt 0}s e ímpar de {\tt 1}s.
        \item O conjunto das palavras em que as posições pares só contêm {\tt 0}s. Exemplos: $\lambda$,
				      {\tt 0}, {\tt 1}, {\tt 00}, {\tt 10}, {\tt 000}, {\tt 001}, {\tt 100}, {\tt 101} etc.
       \end{list}
       Procure ser bem conciso.

 \item Que linguagens são geradas pelas gramáticas a seguir? Procure se expressar como na questão 4, se possível.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $G_1=(\{S,A,B\},\{{\tt a},{\tt b}\},R_1,S)$.
              \begin{enumerate}
               \item[$R_1$:] $S\,\rightarrow\, {\tt a} A \,|\,\lambda$
               \item[\ ]   $A\,\rightarrow\,{\tt b}B$
               \item[\ ]   $B\,\rightarrow\,{\tt a}S$
              \end{enumerate}
        \item $G_2=(\{S,A,B,C\},\{{\tt a},{\tt b}\},R_2,S)$.
              \begin{enumerate}
               \item[$R_2$:] $S\,\rightarrow\, A{\tt a} \,|\, {\tt a}C{\tt a}$
               \item[\ ]   $A\,\rightarrow\,B \,|\, {\tt a}$
               \item[\ ]   $B\,\rightarrow\,A{\tt a} \,|\, {\tt a}C$
              \end{enumerate}
        \item $G_3=(\{K\},\{{\tt a},{\tt b}\},R_3,K)$.
              \begin{enumerate}
               \item[$R_3$:] $K\,\rightarrow\,{\tt a} K {\tt b}\,|\,
                                  {\tt b} K {\tt a} \,|\, \lambda$
              \end{enumerate}
        \item $G_4=(\{P,X,Y\},\{{\tt a},{\tt b}\},R_4,P)$.
              \begin{enumerate}
              \item[$R_4$:] $P\,\rightarrow\,{\tt a} P {\tt a}\,|\,
                                 {\tt b} P {\tt b}\,|\, X$
               \item[\ ]   $X\,\rightarrow\,{\tt a} Y {\tt b} \,|\,
                                {\tt b} Y {\tt a}$
               \item[\ ]   $Y\,\rightarrow\,{\tt a} Y\,|\, {\tt b} Y
                                \,|\, \lambda$
              \end{enumerate}
        \item $G_5=(\{P,A,B,F\},\{{\tt a},{\tt b}\},R_5,P)$.
              \begin{enumerate}
               \item[$R_5$:] $P\,\rightarrow\,{\tt a}AP \,|\,{\tt b}BP\,|\,F$ 
               \item[\ ]  $A{\tt a}\,\rightarrow\,{\tt a}A$
               \item[\ ]  $A{\tt b}\,\rightarrow\,{\tt b}A$
               \item[\ ]  $B{\tt a}\,\rightarrow\,{\tt a}B$
               \item[\ ]  $B{\tt b}\,\rightarrow\,{\tt b}B$
               \item[\ ]  $AF\,\rightarrow\,F{\tt a}$
               \item[\ ]  $BF\,\rightarrow\,F{\tt b}$
               \item[\ ]  $F\,\rightarrow\,\lambda$
              \end{enumerate}
       \end{list}

 \item Obtenha gramáticas para as seguintes linguagens sobre
       $\{{\tt 0},{\tt 1}\}$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ não contém
              {\tt 00}}\}$.
        \item $\{x\overline{x}\,|\, x\in\{{\tt 0},{\tt 1}\}^*\}$. A palavra
              $\overline{x}$ é constituída dos dígitos ``invertidos''
              de $x$. Por exemplo, $\overline{{\tt 0100}}={\tt 1011}$.
        \item $\{{\tt 0}^n{\tt 1}^{2n+1}{\tt 0}^n\,|\, n\geq 0\}$.
        \item $\{x{\tt \#}x\,\,|\,\, x\in\{{\tt 0},{\tt 1}\}^*\}$. Observe que o
              alfabeto tem três símbolos: {\tt 0}, {\tt 1} e {\tt \#}.
       \end{list}

 \item Dos seguintes problemas, quais são problemas de decisão? Quais  são decidíveis?
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\mbox{P}=\mbox{NP}$?
        \item Dado um grafo com custos rotulando suas arestas, determinar o caminho de custo mínimo que
				      passe por cada vértice exatamente uma vez.
        \item Dados um grafo $G$ com custos rotulando suas arestas e um custo $x$, determinar se existe um caminho
				      de custo no mínimo $x$ que passe por cada vértice exatamente uma vez.
        \item Determinar, para qualquer programa em C++, sem entrada, e que tenha, no máximo,
              1GB (antes de compilado), se ele entra em {\em loop} ou não.
       \end{list}

 \item Construa autômatos finitos determinísticos (AFDs) para:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 101}\}^*\{{\tt 010}\}^*$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ não contém {\tt 000} nem {\tt 111}}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, \mbox{ {\tt 000} não é sufixo de $w$}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, |w|\geq 2 \mbox{ e os {\tt 0}s (se houver) precedem os
				        {\tt 1}s (se houver)}\}$.
        \item Conjunto das palavras de $\{{\tt 0},{\tt 1}\}^*$ que contêm um número par de {\tt 0}s ou
				      no máximo três {\tt 0}s.
        \item Conjunto das palavras de $\{{\tt 0},{\tt 1}\}^*$ em que o símbolo na posição $2i$ é diferente daquele
              na posição $2i+2$, para $i\geq 1$. Considere que $\lambda$, {\tt 0}, {\tt 1}, etc. estão no conjunto.
        \item $\{x{\tt 0}^m{\tt 1}{\tt 0}^n\,|\, x\in\{{\tt 0},{\tt 1}\}^*, m+n  \mbox{ é par e $x$ não termina em $0$}\}$.
       \end{list}

 \item Sim ou não? Por que?
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Existe algoritmo que determina se $L(M_1)\subset L(M_2)$ para quaisquer AFDs $M_1$ e $M_2$.
        \item Se um AFD $M$ reconhece alguma palavra de tamanho igual ao número de estados, $k$, de $M$, então
              $|L(M)|> k\times 1000^{1000}$.
        \item Se $X\subseteq Y\subseteq Z$ e existem AFDs que reconhecem $X$ e $Z$, então existe AFD que reconhece $Y$.
        \item Se $X\subseteq Y\subseteq Z$ e não existem AFDs que reconhecem $X$ nem $Z$, então não existe AFD que
              reconhece $Y$.
       \end{list}

 \item Construa autômatos finitos não determinísticos (AFNs) para cada uma das seguintes linguagens, procurando
       utilizar o menor número de estados possível:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt a}\}\cup\{{\tt b}\}^+$. O AFN deve ter apenas um estado final e não pode ter transição $\lambda$.
              (Linz (1997), ex. 8, pág. 64.)
        \item $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\,$ o último símbolo de $w$ tenha ocorrido antes$\}$.
               (Hopcroft et al. (2001), ex. 2.3.4(a), pág. 67.)
        \item $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\,$ o último símbolo de $w$ não tenha ocorrido antes$\}$.
               (Hopcroft et al. (2001), ex. 2.3.4(b), pág. 67.)
        \item $\{x{\tt 1}y\in\{{\tt 0},{\tt 1}\}^*\,|\, |x| \,\mbox{\em mod\/}\, 3 = 1
               \mbox{ e } \eta(y) \,\mbox{\em mod\/}\, 3 = 1\}$, sendo $\eta(y)$ o número representado por $y$ na base 2. 
       \end{list}

 \item Obtenha AFDs equivalentes aos AFNs dos dois primeiros itens da questão anterior, usando o método visto
       no curso ({\em subset construction}).

 \item Prove que os seguintes conjuntos não são linguagens regulares utilizando o lema do bombeamento:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}^ny \,|\, y\in\{{\tt 0},{\tt 1}\}^* \mbox{ e }
                  |y|<n\}$.
        \item $\{{\tt 0}^m{\tt 1}^n \,|\, n<m<2n\}$.
        \item $\{x\overline{x}\,|\, x\in\{{\tt 0},{\tt 1}\}^*\}$.
       \end{list}

 \item Seja $a$ um certo símbolo. Mostre que a classe das linguagens regulares é ou não é fechada sob cada uma das operações:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\mbox{\em pref\/}_a(L)=\{x \,|\, xa\in L \}$.
        \item $\mbox{\em suf\/}_a(L)=\{y \,|\, ay\in L \}$.
        \item $\mbox{\em resto\/}_a(L)=\{xy \,|\, xay\in L \}$.
       \end{list}

 \item Sejam $L_1$ e $L_2$ duas linguagens. Mostre que sim ou que não:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item se $L_1$ e $L_2$ não são regulares, $L_1\cup L_2$ não
                é regular.
          \item se $L_1$ e $L_2$ não são regulares, $L_1\cap L_2$ não
                é regular.
          \item se $L_1$ não é regular, $\overline{L_1}$ não é regular.
          \item se $L_1$ é regular e $L_2$ não é regular,
                $L_1\cup L_2$ não é regular.
          \item se $L_1$ é regular, $L_2$ não é regular e
                $L_1\cap L_2$ é regular, $L_1\cup L_2$ não é regular.
          \item se $L_1$ é regular, $L_2$ não é regular e
                $L_1\cap L_2$ não é regular, $L_1\cup L_2$ não é regular.
         \end{list}
         (Martin (1991), ex. 8.6, pág. 153.)
 \item Construa AFDs que reconheçam as linguagens denotadas pelas expressões regulares (ERs):
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $(aa+b)^*baab$.
        \item $((aa+bb)^*cc)^*$.
       \end{list}
\item Seja o AFD:
      \begin{center}
       \mbox{\setlength{\unitlength}{1mm}
        \begin{picture}(120,28)
         \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

         \node[Nmarks=i](0)(20,25){0}
         \node(1)(40,25){1}
         \node[Nmarks=r](2)(40,5){2}
         \node(3)(20,5){3}

         \drawedge[curvedepth=4](0,1){{\tt a}}
         \drawedge[curvedepth=0](0,3){{\tt b}}
         \drawedge[curvedepth=4](1,0){{\tt a}}
         \drawedge[curvedepth=4](1,2){{\tt b}}
         \drawedge[curvedepth=4](2,1){{\tt b}}
         \drawedge[curvedepth=0](2,3){{\tt a}}

         \drawloop[loopangle=180](3){{\tt a},{\tt b}}
        \end{picture}
       }
      \end{center}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Obtenha uma ER que denote a linguagem reconhecida.
        \item Descreva a linguagem em português.
       \end{list}
 \item Seja o AFD:
       \begin{center}
        \mbox{\setlength{\unitlength}{1mm}
         \begin{picture}(140,20)
          \gasset{Nw=6, Nh=6, Nmr=3, loopdiam=6}

          \node[Nmarks=i](1)(20,8){1}
          \node[Nmarks=r](2)(40,12){2}
          \node[Nmarks=r](3)(60,8){3}

          \drawloop[loopangle=90](1){{\tt b}}
          \drawedge[curvedepth=0](1,2){{\tt a}}
          \drawloop[loopangle=90](2){{\tt a}}
          \drawedge[curvedepth=2](2,3){{\tt b}}
          \drawedge[curvedepth=2](3,2){{\tt a}}
          \drawedge[curvedepth=7](3,1){{\tt b}}
         \end{picture}
        }
      \end{center}
      Obtenha uma ER que denote a linguagem reconhecida.

 \item Obtenha ERs para as seguintes linguagens, a partir de um AFD para as mesmas, usando o métodos visto em aula:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{\verb+0+,\verb+1+\}^*\,|\, w$ n\~ao contém \verb+001+$\}$.
        \item $\{w\in\{\verb+0+,\verb+1+\}^*\,|\, \eta(w) \mbox{ mod } 3 \not= 0\}$.
       \end{list}
 \item Uma ER está na {\bf forma normal disjuntiva} se ela está na forma $r_1+r_2+\cdots+r_n$ para algum $n\geq 1$,
       sendo que nenhuma das subERs $r_i$ contém ocorrência de ``$+$''. Mostre que toda ER é equivalente a uma outra na
			 forma normal disjuntiva. (Lewis \& Papadimitriou (1998), prob. 1.8.7.\footnote{\bf Atenção!
       Serviço de utilidade pública: não compre nem consulte a versão traduzida deste
       livro, pois ela é de péssima qualidade!})

\end{enumerate}

\end{document}
