\documentclass[11pt, a4paper]{report}

\usepackage[brazilian]{babel}
\usepackage[T1]{fontenc} 
\usepackage{fullpage}
\usepackage{gastex}
\usepackage[usenames]{color}

\newcounter{conta}

\begin{document}
 
\noindent {\it Fundamentos da Teoria da Computa\c{c}\~ao}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2013 \\
\noindent Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Lista de Exercícios Preparatória para a Segunda Prova}

\vspace*{3mm}
\begin{enumerate}

 \item Prove que os seguintes conjuntos n\~ao s\~ao linguagens regulares,
       usando o lema do bombeamento:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{x{\tt 1}^n\,|\, n\geq 0, x\in\{{\tt 0},{\tt 1}\}^* \mbox{ e }
              |x|=n\}$.
        \item $\{{\tt 10}^n{\tt 1}^{n}\,|\, n\geq 1\}$.
       \end{list}

 \item Prove que os seguintes conjuntos n\~ao s\~ao linguagens regulares,
       usando propriedades de fecho:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}^m{\tt 1}^{n}\,|\, m\not=n\}$.
        \item $\{w\in \{{\tt 0},{\tt 1}\}^*\,|\, \mbox{ o n\'umero de {\tt 0}s
              em $w$ \'e par e o de {\tt 1}s \'e primo}\}$.
       \end{list}

 \item Sejam as linguagens
       $L_1=\{{\tt 0},{\tt 1}\}^*\{{\tt 1}\}\{{\tt 0},{\tt 1}\}$ e
       $L_2=\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,\eta(w) \mbox{ mod } 3=0\}$, sendo
       $\eta(w)$ o n\'umero representado por $w$ na base dois.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Prove que $L_1-L_2$ \'e regular usando propriedades de fecho.
        \item Construa um aut\^omato finito para $L_1-L_2$.
       \end{list}

 \item Encontre express\~oes regulares para as seguintes linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, |w|\in \{0,1,3\}\}$.
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w$ cont\'em um, dois ou tr\^es
              {\tt b}s$\}$.
        \item $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\,$ o n\'umero de {\tt a}s
               mais o de {\tt b}s em $w$ \'e par$\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w$ cont\'em o s\'{\i}mbolo
              \verb+1+ e $\eta(w) \mbox{ mod } 3=0\}$.
       \end{list}

 \item Obtenha express\~oes regulares que denotem as linguagens sobre
       $\{{\tt 0},{\tt 1}\}$ a seguir, a partir de AFs que reconhe\c cam as
       mesmas, usando o m\'etodo visto em aula. N\~ao simplifique as ERs.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item O conjunto das palavras que come\c{c}am com {\tt 1}, terminam com
              {\tt 1} e t\^em algum {\tt 0}.
        \item O conjunto das palavras que n\~ao cont\'em a subpalavra
              {\tt 0101}.
       \end{list}

 \item Para cada linguagem a seguir, construa um APD com reconhecimento padrão (estado final \underline{e} pilha vazia):
       \begin{list}{(\alph{conta})}{\usecounter{conta}}      
        \item $\{{\tt a}^{2n}{\tt b}^{3n}\,|\,n\geq 0\}$.
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\,w \mbox{ tem um {\tt b} a mais do que {\tt a}s}\}$.
       \end{list}

 \item Construa GLC's para as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}^{2n}{\tt 1}^{3n}\,|\, n\geq 0\}$.
        \item $\{{\tt 0}^n{\tt 1}^n\,|\,n\geq 0\}^2\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,w=w^R\}
              \{{\tt 0}^n{\tt 1}^n\,|\,n\geq 0\}^2$.
        \item $\{{\tt a}^n{\tt b}^{k}{\tt c}^{n+k}\,|\,n,k\geq 0\}$.
        \item $\{{\tt a}^m{\tt b}^n{\tt c}^k\,|\,k\geq m+n\}$.
       \end{list}

 \item Sejam três GLCs $G_1$, $G_2$ e $G_3$. Mostre como construir GLCs para:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $(L(G_1)\cup L(G_2))L(G_3)$.
        \item $L(G_1)^*[L(G_2)L(G_2)\cup (L(G_3)L(G_3))^+]$
       \end{list}

 \item Sejam as gram\'aticas:
       \begin{itemize}
        \item $G_1$: \parbox[t]{10cm}{$X \,\rightarrow\, {\tt a}X \,|\, X{\tt b} \,|\, \lambda$}
        \item $G_2$: \parbox[t]{10cm}{$P \,\rightarrow\, P{\tt ,}P \,|\, P{\tt ;}P \,|\, Z$ \\
                                      $Z \,\rightarrow\, {\tt a}Z \,|\, {\tt b}Z \,|\, \lambda$}
       \end{itemize}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Que linguagens são geradas por $G_1$ e por $G_2$?
        \item Mostre que ambas as gramáticas são amb\'{\i}guas.
        \item Construa uma gram\'atica n\~ao amb\'{\i}gua equivalente a cada uma delas.
       \end{list}

 \item Seja a gram\'atica:
	     \begin{enumerate}
	      \item[\ ] $P\,\rightarrow\, P A A  \,|\,  B \,|\, A {\tt b} \,|\, CD$
	      \item[\ ] $A\,\rightarrow\,{\tt a} A \,|\, B \,|\, BC$
	      \item[\ ] $B\,\rightarrow\,\lambda$
	      \item[\ ] $C\,\rightarrow\, BC$
	      \item[\ ] $D\,\rightarrow\, {\tt b}D \,|\, {\tt bb}$
	     \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se existirem s\'{\i}mbolos in\'uteis, elimine-os.
        \item Elimine regras $\lambda$.
        \item Elimine regras unit\'arias.
        \item Obtenha uma GLC equivalente na forma normal de Chomsky.
       \end{list}
\end{enumerate}

\end{document}
