\documentstyle[12pt]{article}
 
\newcounter{conta}
\newcounter{conta2}
\hyphenation{pro-ble-mas ne-nhum}
\begin{document}
 
\noindent P\'os-Gradua\c{c}\~ao em Ci\^{e}ncia da Computa\c{c}\~{a}o
 \hfill DCC/ICEx/UFMG
 
\noindent {\it Fundamentos Te\'oricos da Computa\c c\~ao}
 \hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2000
 
\noindent Professor: Newton Jos\'{e} Vieira

\noindent {\bf Segunda Lista de Exerc\'{\i}cios} \hfill Data de entrega: 24/10/2000

\section{M\'aquinas de Estado-Finito}

\vspace*{2mm}
\noindent {\large\bf Exerc\'{\i}cios selecionados da Se\c c\~ao 1.3}

\begin{enumerate}
 \item Construa AFN's para as seguintes linguagens sobre $\{\verb+a+,\verb+b+,\verb+c+\}$:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item O conjunto das palavras com, no m\'{\i}nimo, 3 ocorr\^encias de \verb+abc+.
          \item O conjunto das palavras com, no m\'{\i}nimo, 3 ocorr\^encias de \verb+a+'s ou 3
                ocorr\^encias de \verb+b+'s ou 3 ocorr\^encias de \verb+c+'s .
          \item O conjunto das palavras com sufixo \verb+abc+ ou \verb+bca+.
          \item O conjunto das palavras em que existem pelo menos duas ocorr\^encias de \verb+abc+ com um
                n\'umero \'{\i}mpar de s\'{\i}mbolos entre elas.
        \end{list}
 
 \item Sejam as linguagens da forma $L_n=\{xyx\,\,|\,\, x,y\in\{\verb+a+,\verb+b+\}^* \mbox{ e }
       |x|=n\}$.
       Determine o menor n\'umero de
       estados para um AFN e para um AFD que reconhe\c cam $L_n$, nos seguintes casos:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $n=1$
        \item $n=2$
        \item $n$ arbitr\'ario
       \end{list}

 \item Mostre que para todo AFN existe um AFN equivalente com um \'unico estado inicial.

 \item Mostre que sim ou n\~ao: para todo AFN existe um AFN equivalente com um \'unico estado final.

 \item Obtenha um AFD equivalente ao AFN cujo diagrama de estados est\'a mostrado na Figura 1.22
         usando a t\'ecnica do Teorema 7.

 \item Construa AFNE's para as linguagens do exerc\'{\i}cio 1, com um m\'{\i}nimo de transi\c c\~oes
       poss\'{\i}vel.

 \end{enumerate}

\vspace*{2mm}
\noindent {\large\bf Exerc\'{\i}cios selecionados da Se\c c\~ao 1.4}

\begin{enumerate}

 \item Prove que os seguintes conjuntos n\~ao s\~ao linguagens regulares, utilizando o LB:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item $\{\verb+0+^m\verb+1+^n\,\,|\,\, m<n\}$
          \item $\{x \verb+c+ x \,\,|\,\, x\in\{\verb+a+,\verb+b+\}^*\}$
          \item $\{\verb+10+^n\verb+1+^n\,\,|\,\, n\geq 0\}$
          \item $\{\verb+0+^{n^2}\,\,|\,\, n\geq0\}$
         \end{list}

 \item Prove que os seguintes conjuntos n\~ao s\~ao linguagens regulares, utilizando propriedades de
         fechamento:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item $\{\verb+0+,\verb+1+\}^*-\{\verb+0+^n\verb+1+^n\,\,|\,\, n\geq 0\}$
          \item $\{\verb+0+^m\verb+1+^n\,\,|\,\, m<n\}\cup\{\verb+0+^m\verb+1+^n\,\,|\,\, m>n\}$
          \item $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\,$ o n\'umero de \verb+0+'s em $w$ \'e igual ao
                n\'umero de \verb+1+'s$\}$
          \item $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\,$ o n\'umero de \verb+0+'s em $w$ \'e igual ao
                n\'umero de \verb+1+'s$\}$  $-\{\verb+0+^n\verb+1+^n\,\,|\,\, n\geq 0\}$
         \end{list}

 \item Complete o Exemplo 74: utilizando a receita dada l\'a, obtenha um AFD que reconhe\c ca
       a linguagem constitu\'{\i}da de todas as palavras bin\'arias que representem n\'umeros
       divis\'{\i}veis por 6, com exce\c c\~ao daquelas em que o terceiro d\'{\i}gito da direita para
       a esquerda seja \verb+1+.

 \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\~ao a $\Sigma_1$) que t\^em
       como sufixo alguma palavra de $L$ \'e linguagem regular.
\end{enumerate}

\vspace*{2mm}
\noindent {\large\bf Exerc\'{\i}cios selecionados da Se\c c\~ao 1.5}

\begin{enumerate}	
 \item Construa uma m\'aquina de Moore que determine o resto da divis\~ao por 3 de um n\'umero na
       representa\c c\~ao bin\'aria.

 \item Construa uma m\'aquina de Moore que determine a quantidade de \verb+1+'s presentes nos \'ultimos
       3 d\'{\i}gitos de palavras sobre $\{\verb+0+,\verb+1+\}$.

 \item Construa uma m\'aquina de Mealy que determine o quociente da divis\~ao por 3 de um n\'umero na
       representa\c c\~ao bin\'aria.

 \item Construa uma m\'aquina de Mealy que some dois n\'umeros na base bin\'aria. Os n\'umeros devem ser
       supridos por meio do alfabeto $\{[\verb+0+,\verb+0+],[\verb+0+,\verb+1+],[\verb+1+,\verb+0+],
      [\verb+1+,\verb+1+]\}$, d\'{\i}gitos menos significativos em primeiro lugar. Por exemplo, para
      somar os n\'umeros 13 e 20, pode-se suprir a palavra $[\verb+0+,\verb+1+][\verb+1+,\verb+0+]
      [\verb+1+,\verb+1+][\verb+0+,\verb+0+][\verb+1+,\verb+0+]$, onde os primeiros d\'{\i}gitos,
      \verb+01101+, codificam o n\'umero 13, e os segundos, \verb+10100+, codificam o n\'umero 20;
      neste caso, a sa\'{\i}da deve ser \verb+100001+, que codifica o n\'umero 33.

\end{enumerate}

\vspace*{2mm}
\noindent {\large\bf Exerc\'{\i}cios selecionados da Se\c c\~ao 1.6}

\begin{enumerate}	
 \item Mostre que sim ou que n\~ao: 
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item Para qualquer linguagem $L$ (inclusive aquelas que n\~ao s\~ao regulares), existem
                linguagens regulares $R_1$ e $R_2$ tais que $R_1\subseteq L\subseteq R_2$.
          \item Todos os subconjuntos de uma linguagem regular s\~ao tamb\'em linguagens regulares.
          \item H\'a linguagens regulares que t\^em como subconjuntos linguagens que n\~ao s\~ao
                regulares.
          \item A uni\~ao de duas linguagens que n\~ao s\~ao regulares pode ser ou n\~ao uma linguagem
                regular.
          \item A interse\c c\~ao de duas linguagens que n\~ao s\~ao regulares pode ser ou n\~ao uma
                linguagem regular.
          \item O complemento de uma linguagem que n\~ao \'e regular pode ser ou n\~ao uma linguagem
                regular.
         \end{list}

 \item Mostre que a classe das linguagens regulares \'e fechada sob as seguintes opera\c c\~oes:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item $\mbox{\em pref\/}(L)=\{x \,\,|\,\, xy\in L \}$ (os prefixos das palavras de $L$)
          \item $\mbox{\em suf\/}(L)=\{y \,\,|\,\, xy\in L \}$ (os sufixos das palavras de $L$)
          \item $\mbox{\em rev\/}(L)=\{w^R \,\,|\,\, w\in L\}$ (os reversos das palavras de $L$)
         \end{list}

 \item Sejam $L_1,L_2,\ldots$ linguagens regulares e seja uma constante $n\geq 2$. Mostre que:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item $\bigcup_{2\leq i\leq n}L_i$ \'e uma linguagem regular.
          \item $\bigcup_{i\geq 2}L_i$ pode n\~ao ser uma linguagem regular.
         \end{list}

 \item Sejam $L$ uma linguagem n\~ao regular, e seja $F$ uma linguagem finita. Mostre que:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item $L\cup F$ n\~ao \'e linguagem regular.
          \item $L-F$ n\~ao \'e linguagem regular.
         \end{list}
         Mostre que ambos os resultados n\~ao s\~ao verdadeiros se for suposto que $F$ \'e linguagem
         regular, mas n\~ao finita.

 \item Sejam $L_1$ e $L_2$ duas linguagens. Mostre que sim ou que n\~ao:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item se $L_1\cup L_2$ \'e uma linguagem regular ent\~ao $L_1$ \'e uma linguagem regular.
          \item se $L_1L_2$ \'e uma linguagem regular ent\~ao $L_1$ \'e uma linguagem regular.
          \item se $L_1^*$ \'e uma linguagem regular ent\~ao $L_1$ \'e uma linguagem regular.
          \item se $L_1$ \'e uma linguagem regular ent\~ao $\{w \,\,|\,\, w $ \'e uma subpalavra de
                $L_1\}$ \'e uma linguagem regular.
         \end{list}
\end{enumerate}

\section{ER's, GR's e GR's}

\vspace*{2mm}
\noindent {\large\bf Exerc\'{\i}cios selecionados da Se\c c\~ao 2.1}

\begin{enumerate}
 \item Descreva, em portugu\^es, as linguagens sobre $\{\verb+0+,\verb+1+\}$ denotadas pelas seguintes
       ER's:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item $0(0+1)^*1$
          \item $0^*(0+1)1^*$
          \item $(0+1)^*1(0+1)(0+1)$
          \item $(0+\lambda)(10+1)^*$
         \end{list}

 \item Encontre (diretamente) express\~oes regulares que denotem os seguintes conjuntos:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\, |w|\geq 3\}$
          \item $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\, w$ come\c ca com \verb+a+ e tem tamanho par$\}$
          \item $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\, w$ tem n\'umero par de \verb+a+'s$\}$
          \item $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\, w$ cont\'em \verb+bb+$\}$
          \item $\{w\in\{\verb+a+,\verb+b+\}^*\,\,|\,\, w$ cont\'em exatamente um \verb+bb+$\}$
         \end{list}

 \item Considere o diagrama ER da Figura 2.3(b). Simplifique a ER correspondente, $q^*r(s+tq^*r)^*$,
       para todas as $2^4$ possibilidades de se atribuir $\emptyset$ \`as express\~oes b\'asicas $q$,
       $r$, $s$ e $t$.

 \item Obtenha ER's que denotem as seguintes linguagens sobre $\{\verb+0+,\verb+1+\}$,
         a partir de um AFD para as mesmas, usando o algoritmo da Figura 2.4:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item O conjunto das palavras de tamanho maior que 1 tais que os \verb+0+'s (se houver algum)
                precedem os \verb+b+'s (se houver algum).
          \item O conjunto das palavras que come\c cam com \verb+1+ e terminam com \verb+1+.
          \item O conjunto das palavras que come\c cam com \verb+1+, terminam com \verb+1+ e t\^em pelo
                menos um \verb+0+.
          \item O conjunto das palavras com n\'umeros \'{\i}mpar de \verb+0+'s e \'{\i}mpar de
                \verb+1+'s.
         \end{list}

 \item Que tipo de linguagem pode ser denotada por uma ER sem ocorr\^encias de fecho de Kleene?
\end{enumerate}

\vspace*{2mm}
\noindent {\large\bf Exerc\'{\i}cios selecionados da Se\c c\~ao 2.2}

\begin{enumerate}
 \item Obtenha GR's para as seguintes linguagens sobre \{\verb+0+,\verb+1+\}:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
         \item $\emptyset$
         \item $\{\lambda\}$
         \item O conjunto das palavras com tamanho m\'ultiplo de 3.
         \item O conjunto das palavras com um n\'umero par de \verb+0+'s e um n\'umero par de \verb+1+'s.
         \item O conjunto das palavras em que cada \verb+0+ \'e seguido imediatamente de, no m\'{\i}nimo,
               dois \verb+1+'s.
         \item O conjunto das palavras em que o antepen\'ultiplo s\'{\i}mbolo \'e \verb+1+.
         \end{list}

 \item Alguns autores definem uma gram\'atica regular como sendo uma gram\'atica em que as regras s\~ao
       da forma $X\rightarrow xY$ e $X\rightarrow x$, onde $X$ e $Y$ s\~ao vari\'aveis e $x$ \'e uma
       palavra de terminais. Mostre como obter uma GR equivalente a uma gram\'atica com regras desta
       forma.

 \item Responda \`as seguintes perguntas, justificando suas respostas:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Quantas regras, no m\'{\i}nimo, s\~ao necess\'arias para gerar uma linguagem infinita?
        \item Dada uma express\~ao regular, \'e poss\'{\i}vel obter uma GR que gera a linguagem denotada
              por ela?
        \item \'E poss\'{\i}vel gerar qualquer linguagem finita por meio de GR?
        \item Dada uma GR \'e poss\'{\i}vel obter uma outra GR equivalente em que a gera\c c\~ao de
              qualquer palavra \'e determin\'{\i}stica (em qualquer passo da deriva\c c\~ao existe uma
              \'unica regra aplic\'avel)?
       \end{list}
\end{enumerate}

\vspace*{2mm}
\noindent {\large\bf Exerc\'{\i}cios selecionados da Se\c c\~ao 2.4}

\begin{enumerate}

 \item Determine express\~oes regulares e gram\'aticas regulares para as seguintes linguagens sob
       $\{\verb+0+,\verb+1+\}^*$:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Conjunto das palavras em que \verb+0+'s s\'o podem ocorrer nas posi\c c\~oes pares.
        \item Conjunto das palavras que n\~ao cont\^em \verb+000+.
        \item Conjunto das palavras em que cada subpalavra de tamanho 4 cont\'em pelo menos 3 \verb+1+'s.
        \item Conjunto das palavras que n\~ao cont\^em \verb+00+ nos \'ultimos 4 s\'{\i}mbolos.
        \item Conjunto das palavras que n\~ao cont\^em \verb+00+, a n\~ao ser nos \'ultimos 4
              s\'{\i}mbolos (se tiver).
       \end{list}

 \item Sejam as seguintes ER's:
         \begin{itemize}
          \item $r_1=(a+b)^*(ab+ba)(a+b)^*$
          \item $r_2=ab^*$
          \item $r_3=a(b^*ab^*a)^*$
          \item $r_4=(aa+bb+(ab+ba)(aa+bb)^*(ab+ba))^*$
         \end{itemize}
         Encontre ER's para:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item $\overline{L(r_1)}$
          \item $\overline{L(r_2)}$
          \item $\overline{L(r_3)}$
          \item $\overline{L(r_4)}$
          \item $L(r_1)\cap L(r_4)$
          \item $L(r_1)-L(r_4)$
         \end{list}

 \item Considere que as transi\c c\~oes especificadas em um diagrama ER sobre $\Sigma$ representam uma
       fun\c c\~ao $\delta:E\times R\rightarrow {\cal P}(E)$, onde $E$ \'e o conjunto de estados e $R$
       \'e o conjunto (obviamente finito) das ER's sobre $\Sigma$ que ocorrem no diagrama. Defina uma
       fun\c c\~ao $\hat{\delta}:{\cal P}(E)\times \Sigma^*\rightarrow {\cal P}(E)$ tal que
       $\hat{\delta}(X,w)$ seja o conjunto dos estados alcan\c c\'aveis a partir dos estados de $X$,
       consumindo-se a palavra $w$. Para facilitar a tarefa, defina antes a fun\c c\~ao auxiliar
       $f\!\lambda:{\cal P}(E)\rightarrow{\cal P}(E)$ tal que $f\!\lambda(X)$ seja o conjunto dos
       estados alcan\c c\'aveis a partir dos estados de $X$, sem consumo de s\'{\i}mbolos.
       (Use a nota\c c\~ao $L(r)$ significando ``o conjunto denotado pela ER $r$''.)

 \item Defina a linguagem especificada por um diagrama ER utilizando a fun\c c\~ao $\hat{\delta}$ do
       exerc\'{\i}cio anterior.

 \item GR's s\~ao tamb\'em denominadas {\em gram\'aticas lineares \`a direita\/}. Uma gram\'atica \'e
       dita {\em linear \`a esquerda\/} se ela s\'o cont\'em regras das formas $X\rightarrow Ya$,
       $X\rightarrow a$ e $X\rightarrow \lambda$, onde $X$ e $Y$ s\~ao vari\'aveis e $a$ \'e terminal.
       Mostre que a classe das linguagens geradas por gram\'aticas lineares
       \`a esquerda \'e a classe das linguagens regulares.

 \item Seja um tipo de gram\'atica cujas regras sejam das formas $X\rightarrow aY$, $X\rightarrow Ya$,
       $X\rightarrow a$ e $X\rightarrow \lambda$, onde $X$ e $Y$ s\~ao vari\'aveis e $a$ \'e terminal.
       Com este tipo de gram\'atica \'e poss\'{\i}vel gerar linguagem que n\~ao seja regular?

\end{enumerate}


\end{document}
 
