\documentclass[11pt]{report}

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

\newcounter{conta}
\pagestyle{empty}

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

\vspace*{3mm}
\begin{enumerate}
 \item Usando o teorema da invariância à direita, mostre que os seguintes conjuntos não são linguagens regulares:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}^nx\,|\, x\in\{{\tt 0},{\tt 1}\}^* \mbox{ e } |x|<n\}$;
        \item $\{xx \,|\, x\in \{{\tt 0},{\tt 1}\}^*\}$;
        \item $\{xx^Rx \,|\, x\in \{{\tt 0},{\tt 1}\}^*\}$.
       \end{list}
 \item Prove que os seguintes conjuntos anteriores não são linguagens regulares, utilizando o LB.
 \item Prove que os seguintes conjuntos não são linguagens regulares, utilizando pro\-prie\-da\-des de fechamento:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $\{{\tt 0}^m{\tt 1}^n\,|\, m<n\}\cup\{{\tt 0}^m{\tt 1}^n\,|\, m>n\}$;
        \item $\{x{\tt 1}y\in\{{\tt 0},{\tt 1}\}^*\,|\, n_{\tt 0}(x)=n_{\tt 1}(y)\}$;
        \item $\{x{\tt 1}^n\,|\, x\in\{{\tt 0},{\tt 1}\}^* \mbox{ e } |x|\leq n\}$;
        \item $\{w\in\{{\tt 0},{\tt 1},{\tt 2}\}^*\,|\, n_{\tt 0}(w)\not=n_{\tt 1}(w)\}$.
       \end{list}
 \item Sejam $L_1=\{{0}^n \,|\, n \mbox{ é um número primo}\}$ e $L_2=\{{\tt 0}^k\}\{{\tt 0}\}^*$,
       em que $k$ é uma constante. Para cada linguagem a seguir, mostre que ela é regular ou que
			 não é:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $L_1-L_2$;
        \item $L_1\cap L_2$;
        \item $L_1\cup L_2$.
       \end{list}
 \item Seja $L$ uma linguagem regular sobre um alfabeto $\Sigma_1$. Prove que o conjunto de todas as palavras sobre
       $\Sigma_2$ (que pode ser igual ou não a $\Sigma_1$) que têm como sufixo alguma palavra de $L$ é linguagem regular.
 \item Inspirado no Exemplo 54 do livro, construa máquinas de Moore que determinem o número de ocorrências da
       subpalavra {\tt 101} em uma palavra de entrada no alfabeto $\{{\tt 0},{\tt 1}\}$, nos casos:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
			  \item Sem contar ocorrências superpostas de subpalavras.
				\item Contando, inclusive, ocorrências superpostas.
       \end{list}
			 Por exemplo, {\tt 101010} tem apenas um ocorrência no primeiro critério (apenas a primeira deve ser detectada), mas
			 tem duas no segundo.
 \item Faça uma máquina de Moore que: (a) caso a palavra de entrada termine em {\tt 010}, apresente {\tt a} como saída; (b) caso
       ela termine em {\tt 101}, dê {\tt b} como saída; e (c) a saída seja {\tt c}, caso contrário. O alfabeto de entrada é
			 $\{{\tt 0},{\tt 1}\}$.
 \item Construa uma máquina de Mealy que determine o quociente da divisão por 3 de um número na representação binária.
 \item Construa uma máquina de Mealy de alfabetos de entrada e de saída iguais a $\{{\tt 0},{\tt 1}\}$ que emita como saída
       a própria entrada a partir de seu terceiro símbolo; os dois primeiros símbolos emitidos na saída devem ser {\tt 0}s e os
			 dois últimos símbolos de entrada não devem ter correspondentes de saída. Por exemplo:
			 \begin{tabbing}
			  xxx\= entrada:x \= \ \ 4\= \ \ 4\= \ \ 4\= \ \ 4\= \ \ 4\= \ \ 4\= \ \ 4\= \ \ 4\=  \kill
				   \> entrada:  \> 1\> 0\> 0\> 1\> 1\> 0\> 1\> 1\> $\cdots$ \\
				   \> saída:    \> 0\> 0\> 1\> 0\> 0\> 1\> 1\> 0\> $\cdots$
			 \end{tabbing}
       Mais formalmente, a função de saída deve ser tal que $s(i,{\tt 0})=s(i,{\tt 1})={\tt 0}$, e $s(i,xy)={\tt 00}x$ para
			 $|y|=2$.
 \item Encontre expressões regulares que denotem os conjuntos:
         \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
          \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w$ contém no máximo três {\tt b}s$\}$;
          \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w$ tem número ímpar de {\tt a}s$\}$;
          \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w$ contém {\tt aba}$\}$;
          \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w$ contém exatamente um {\tt ab}$\}$;
          \item $\{w\in\{{\tt a},{\tt b}\}^*\,|\, w$ contém exatamente um {\tt bb}$\}$.
         \end{list}
 \item Construa um AFD para cada uma das linguagens denotadas pelas ERs:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $(ab)^*ac$;
        \item $(ab)^*(ba)^*$;
        \item $(ab^*a)^*(ba^*b)^*$;
        \item $(aa+b)^*baab$.
       \end{list}
 \item \label{eafder} Construa ERs que denotem as linguagens reconhecidas pelos AFs mostrados na Figura~\ref{feafder}, utilizando o método descrito no livro.
       \label{eafder}
       \begin{figure}
        \begin{center} \setlength{\unitlength}{1mm}
         \begin{picture}(40,37)
          \gasset{Nw=6, Nh=6, Nmr=4, ELdist=0.5, loopdiam=5, fillgray=0.9}

          \node[Nmarks=i](0)(10,32){0}
          \node(1)(30,32){1}
          \node[Nmarks=r](2)(30,12){2}
          \node(3)(10,12){3}

          \drawedge[curvedepth=3](0,1){\tt a}
          \drawedge[curvedepth=0](0,3){\tt b}
          \drawedge[curvedepth=3](1,0){\tt a}
          \drawedge[curvedepth=3](1,2){\tt b}
          \drawedge[curvedepth=3](2,1){\tt b}
          \drawedge[curvedepth=0](2,3){\tt a}
          \drawloop[loopangle=225](3){{\tt a},{\tt b}}
					\put(20,5){\makebox(0,0)[ct]{\bf (a)}}
         \end{picture}
         \begin{picture}(40,37)
          \gasset{Nw=6, Nh=6, Nmr=4, ELdist=0.5, loopdiam=5, fillgray=0.9}

          \node[Nmarks=i](0)(10,22){0}
          \node(1)(25,32){1}
          \node(2)(25,12){2}
          \node[Nmarks=r](3)(40,22){3}

          \drawedge[curvedepth=0](0,1){{\tt a},{\tt b}}
          \drawedge[curvedepth=0,ELside=r](0,2){\tt a}
          \drawedge[curvedepth=3](1,2){\tt a}
          \drawedge[curvedepth=0](1,3){\tt b}
          \drawedge[curvedepth=3](2,1){\tt b}
          \drawedge[curvedepth=0,ELside=r](2,3){\tt b}
					\put(25,5){\makebox(0,0)[ct]{\bf (b)}}
         \end{picture}
         \begin{picture}(40,37)
          \gasset{Nw=6, Nh=6, Nmr=4, ELdist=0.5, loopdiam=5, fillgray=0.9}

          \node[Nmarks=i](0)(20,32){0}
          \node(1)(40,32){1}
          \node[Nmarks=ir](2)(30,12){2}

          \drawloop[loopangle=90](0){\tt a}
          \drawedge[curvedepth=0](0,1){\tt a}
          \drawloop[loopangle=0](1){\tt b}
          \drawedge[curvedepth=3](1,2){\tt c}
          \drawloop[loopangle=0](2){\tt c}
          \drawedge[curvedepth=3](2,1){\tt b}
          \drawedge[curvedepth=0](2,0){\tt a}
					\put(30,5){\makebox(0,0)[ct]{\bf (c)}}
         \end{picture}
        \end{center}

        \caption{\label{feafder} AFs do Exercício \ref{eafder}.}
       \end{figure}
 \item Obtenha GRs para as seguintes linguagens sobre \{{\tt 0},{\tt 1}\}:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
       \item o conjunto das palavras com tamanho múltiplo de 3;
       \item o conjunto das palavras em que cada {\tt 0} é seguido imediatamente de, no mínimo, dois {\tt 1}s;
       \item o conjunto das palavras em que cada {\tt 0} ocorre entre dois {\tt 1}s;
       \item o conjunto das palavras em que o antepenúltimo símbolo é {\tt 1};
       \item o conjunto das palavras que não contêm {\tt 0}s consecutivos nem {\tt 1}s consecutivos.
      \end{list}

 \item Seja a GR $G=(\{P,A,B\},\{{\tt a},{\tt b}\},R,P)$, em que $R$ consta das regras:
       \begin{quote}
        $P \,\rightarrow\, {\tt a}P \,|\, {\tt b}P \,|\, {\tt a}A$ \\
        $A \,\rightarrow\, {\tt a} \,|\, {\tt b}B$ \\
        $B \,\rightarrow\, {\tt b}A$
       \end{quote}
       Construa, a partir de $G$, um AFN que aceite $L(G)$.
% \item Construa APDs para as seguintes linguagens:
%         \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
%          \item $\{{\tt 0}^n{\tt 1}^{2n}\,|\,n\geq 0\}$;
%          \item $\{{\tt 0}^{3n}{\tt 1}^{2n}\,|\,n\geq 0\}$;
%          \item $\{w{\tt 0}w^R\,|\,w\in\{{\tt 1},{\tt 2}\}^*\}$;
%          \item $\{{\tt a}^n{\tt b}^k{\tt c}^n \,|\, n,k\geq 0\}$;
%          \item $\{{\tt a}^n{\tt b}^i{\tt c}^j \,|\, n=i+j\}$.
%          \end{list}
 \item Para as seguintes linguagens, construa APD, se possível. Se não for possível, construa APN.
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $\{({\tt 01})^n{\tt 1}({\tt 10})^n\,|\,n\in\mathbb{N}\}$;
        \item $\{({\tt 01})^n{\tt 0}({\tt 10})^n\,|\,n\in\mathbb{N}\}$;
        \item $\{{\tt a}^n{\tt b}^{2n}{\tt c}^{2k}\,|\,n,k\in\mathbb{N}\}$;
        \item $\{{\tt a}^n{\tt b}^{2n}{\tt a}^{2k}\,|\,n\geq 1,k\in\mathbb{N}\}$.
       \end{list}
 \item Construa APDs que reconheçam $\{{\tt a}^n{\tt b}^n\,|\, n\geq 0\}$:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item por estado final;
        \item por pilha vazia.
       \end{list}
 \item Seja um AP cuja pilha pode conter, no máximo, $n$ símbolos. Que limitações
       terá tal tipo de AP? Justifique sua resposta.
 \item Mostre como obter um APN $P$ a partir de um AFN$\lambda$ $M$, tal que $L(P)=L(M)$, e
       que $P$ deve ter apenas dois estados e a pilha deve conter no
       máximo um símbolo. \emph{Dica}: Faça o alfabeto de pilha igual ao
       conjunto de estados do AFN$\lambda$.
 \item Construa GLCs que gerem:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $L_1=\{{\tt a}^m{\tt b}^n \,|\, m\not=n\}$;
        \item $L_2=\{{\tt a}^{m+n}{\tt b}^{m}{\tt c}^{n} \,|\, m \mbox{ é par e } n \mbox{ é ímpar}\}$;
	      \item $L_1(L_1\cup L_2)^*L_2$.
       \end{list}
 \item Dadas duas GLCs $G_1=(V_1,\Sigma_1,R_1,P_1)$ e $G_2=(V_2,\Sigma_2,R_2,P_2)$,
       tais que $V_1\cap V_2=\emptyset$, como seriam obtidas GLCs para gerar:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}\setlength{\topsep}{0.01mm}\setlength{\itemsep}{0.01mm}
        \item $(L(G_1)L(G_2))\cup (L(G_2)L(G_1))$?
        \item $L(G_1)^+L(G_2)^*$?
        \item $(L(G_1)\cup L(G_2))^*L(G_2)^+$?
       \end{list}
 \item Crie GLCs para:
       \begin{list}{\bf \alph{conta})}{\usecounter{conta}}
        \item $L_1=\{{\tt 0}^n{\tt 1}^k\,|\, 2n\leq k \leq 3n\}$;
        \item $L_2=\{{\tt a}^n{\tt b}^k{\tt c}^m\,|\,k=2n+m\}$.
       \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}{\bf \alph{conta})}{\usecounter{conta}}
	 \item Desenvolva uma DME 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 Mostre que a GLC a seguir é ambígua:
      \begin{enumerate}
       \item[\ ] $E\,\rightarrow\, {\tt a}R\,|\,{\tt (}E{\tt )}R\,|\,{\tt a} \,|\,  {\tt (}E{\tt )}$
       \item[\ ] $R\,\rightarrow\, {\tt +}ER\,|\,{\tt *}ER\,|\,\lambda$
      \end{enumerate}
 \item Seja a GLC $G$:
       \begin{enumerate}
        \item[\ ]$S \,\rightarrow\, {\tt 0}S{\tt 0} \,|\, {\tt 1}A{\tt 1}$
        \item[\ ]$A \,\rightarrow\, {\tt 0}A{\tt 0} \,|\, {\tt 1}$
       \end{enumerate}
       Obtenha GLCs equivalentes:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item na forma normal de Chomsky;
        \item na forma normal de Greibach.
       \end{list}
 \item Construa uma gramática sem regras $\lambda$ equivalente à gramática a seguir e, em seguida,
       elimine símbolos inúteis:
	     \begin{enumerate}
        \item[\ ] $S\,\rightarrow\, A {\tt a} B \,|\, {\tt aa} B$
	      \item[\ ] $A\,\rightarrow\, \lambda$
        \item[\ ] $B\,\rightarrow\, {\tt bb} A \,|\, \lambda$
       \end{enumerate}
 \item Obtenha uma GLC na forma normal de Chomsky que gere $L(G)-\{\lambda\}$, se:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $G$ tem as regras	\parbox[t]{12cm}{$P\,\rightarrow\, P(P) \,|\, \lambda$}
        \item $G$ tem as regras	\parbox[t]{12cm}{$P\,\rightarrow\, ABA$ \\
				            $A\,\rightarrow\, {\tt a}A \,|\, \lambda$ \\ $B\,\rightarrow\, {\tt b}B \,|\, \lambda$}
      	\end{list}
 \item Seja a GLC $G$:
       \begin{enumerate}
        \item[\ ] $E\,\rightarrow\, E{\tt +}E \,|\, E{\tt *}E
                              \,|\, {\tt a}$
       \end{enumerate}
       Construa uma gramática na FNG equivalente a $G$.
 \item Obtenha uma GLC na FNG que gere $\{{\tt a}^m{\tt b}^n{\tt c}^k \,|\, n>m+k\}$. Em seguida, construa
       um AP que reconheça a mesma linguagem, a partir da GLC construída, de acordo com o método visto.

\end{enumerate}

\end{document}
