\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ção} \hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2015 \\
\noindent Professor: Newton José Vieira \hfill DCC/ICEx/UFMG \\
\noindent {\bf Segunda Lista de Exercícios} \\
\noindent \emph{Data de entrega}: até 16:40h de 14/05/2015. Local: sala 4023 ou em sala de aula.

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

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

 \item Prove que os seguintes conjuntos não são 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úmero de {\tt 0}s em $w$ é par e o de {\tt 1}s é primo}\}$.
       \end{list}

 \item Suponha que $L$ seja uma linguagem regular de alfabeto $\Sigma=\{{\tt a},{\tt b},{\tt c}\}$. Mostre que cada uma das 
       linguagens a seguir é regular:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in L\,|\, \mbox{$w$ contém pelo menos um {\tt a}}\}$;
        \item $\{w\,|\, \mbox{$w\in L$ ou $w$ contém pelo menos um {\tt a}, \underline{ou ambos}}\}$;
        \item $\{w\,|\, \mbox{$w\in L$ ou $w$ contém pelo menos um {\tt a}, \underline{mas não ambos}}\}$;
        \item $\{w\in \Sigma^* \,|\, w\not\in L \mbox{ e $w$ não contém {\tt a}s}\}$.
       \end{list}

 \item Encontre ERs que denotem as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w$ contém um ou dois {\tt b}s$\}$.
        \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w$ começa com {\tt a} e tem número par de {\tt b}s$\}$.
        \item $\{w\in\{{\tt a},{\tt b},{\tt c}\}^*\,|\,$ o número de {\tt a}s mais o de {\tt b}s em $w$ é par$\}$.
       \end{list}

 \item Obtenha ERs que denotem as linguagens sobre $\{{\tt 0},{\tt 1}\}$ a seguir, a partir de AFs
       que reconheçam as mesmas, usando o método visto em aula.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ não termina em {\tt 11}}\}$.
        \item $\{w\in\{{\tt 0},{\tt 1}\}^*\,|\, w \mbox{ tem exatamente uma ocorrência da subpalavra {\tt 00}}\}$.
       \end{list}

 \item Construa um AFD para cada uma das linguagens denotadas pelas ERs:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $(ab)^*ac$
        \item $(ab)^*(ba)^*$
        \item $(ab^*a)^*(ba^*b)^*$
       \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{\tt 2}w^R\,|\, w\in\{{\tt 0},{\tt 1}\}^*\}$.
       \end{list}

\pagebreak
 \item Para cada linguagem a seguir, construa um APD, se possível. Caso contrário, faça um APN. O reconhecimento deve ser o
       padrão (estado final \underline{e} pilha vazia).
       \begin{list}{(\alph{conta})}{\usecounter{conta}}      
        \item $\{{\tt a}^{2n}{\tt b}^{3n}\,|\,n\geq 0\}\cup\{{\tt a}^{3n}{\tt b}^{2n}\,|\,n\geq 0\}$.
        \item $\{w{\tt 0}w^R\,|\, w\in\{{\tt 0},{\tt 1}\}^*\}$.
       \end{list}

  \item Seja $G$ a gramática:
	\begin{enumerate}
	 \item[\ ] $P \,\rightarrow\, A B$
	 \item[\ ] $A \,\rightarrow\, {\tt a} A {\tt b} \,|\, {\tt c}$
	 \item[\ ] $B \,\rightarrow\, {\tt b} B {\tt c} \,|\, {\tt a}$
	\end{enumerate}
	\begin{list}{(\alph{conta})}{\usecounter{conta}}
	 \item Desenvolva uma derivação mais à esquerda de {\tt acbbbacc}. 
	 \item Monte a árvore de derivação para a derivação construída em (a).
	 \item Defina $L(G)$ utilizando notação de conjunto.
	\end{list}

 \item Construa GLCs para as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{{\tt a}^{2n}{\tt b}^{3n}\,|\,n\geq 0\}\cup\{{\tt a}^{3n}{\tt b}^{2n}\,|\,n\geq 0\}$.
        \item $(\{{\tt 0}^n{\tt 1}^n\,|\,n\geq 0\}^{\bf 2}\{w\in\{{\tt 0},{\tt 1}\}^*\,|\,w=w^R\})\cup\{ww^R\,|\,
				       w\in\{{\tt 0},{\tt 1}\}^*$.
        \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 as gramáticas:
       \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 \textbf{,} P \,|\, P \textbf{;} 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íguas.
        \item Construa uma gramática não ambígua equivalente a cada uma delas.
       \end{list}

 \item Construa uma GLC sem regras $\lambda$ equivalente à seguinte gramática a seguir. Comece apresentando o conjunto das
       variáveis anuláveis.
       \begin{enumerate}
	      \item[\ ] $P\,\rightarrow\, B P A \,|\, A$
	      \item[\ ] $A\,\rightarrow\, {\tt a} A \,|\, \lambda$
	      \item[\ ] $B\,\rightarrow\, B {\tt b} {\tt a} \,|\, \lambda$
	     \end{enumerate}

\pagebreak
  \item Seja a gramática $G$:
	      \begin{enumerate}
	       \item[\ ] $P\,\rightarrow\,A \,|\, B C $
	       \item[\ ] $A\,\rightarrow\,B \,|\, C$
	       \item[\ ] $B\,\rightarrow\,{\tt b} B \,|\, {\tt b}$
	       \item[\ ] $C\,\rightarrow\,{\tt c} C \,|\, {\tt c}$
	      \end{enumerate}
	      \begin{list}{(\alph{conta})}{\usecounter{conta}}
	       \item Crie uma gramática equivalente a $G$, sem regras de cadeias. Comece com $\mbox{enc}(X)$ para cada $X$.
	       \item Mostre que a gramática construída contém símbolos inúteis.
	      \end{list}

 \item Seja a gramática:
	     \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}
			 Seguindo todos os passos dos métodos vistos em aula e explicitando cada um deles:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se existirem símbolos inúteis, elimine-os.
        \item Elimine regras $\lambda$.
        \item Elimine regras unitárias.
        \item Obtenha uma GLC equivalente na forma normal de Chomsky.
       \end{list}
\end{enumerate}

\end{document}
