\documentclass[12pt]{report}

\addtolength{\textheight}{1cm}
\pagestyle{empty}
\newcounter{conta}
\begin{document}

\noindent Bacharelado em Ci\^encia da Computa\c c\~ao \hfill DCC/ ICEx/UFMG \\
\noindent {\em Fundamentos da Teoria da Computa\c c\~ao} \hfill $1^{\mbox{\underline{o}}}$ semestre de 2002 \\
\noindent Professor: Newton Jos\'e Vieira \\
\noindent {\bf Primeira Prova} \hfill 11/07/2002 \hfill {\bf Dura\c c\~ao: 1h:40m} \\
\noindent {\bf Turmas A}

\vspace*{2mm}
\noindent {\bf Cada item de cada quest\~ao vale 1 ponto.}

\vspace*{1mm}
\begin{enumerate}
 \item Expresse as linguagens a seguir utilizando opera\c c\~oes sobre conjuntos
       finitos de palavras de $\{\verb+0+,\verb+1+\}^*$. Considere o alfabeto
       como sendo $\{\verb+0+,\verb+1+\}$.
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item O conjunto das palavras que t\^em de 5 a 10 s\'{\i}mbolos.
          \item O conjunto das palavras que n\~ao tenham \verb+00+ como subpalavra,
                nem \verb+11+. Exemplos: $\lambda$, \verb+0+, \verb+01+,
                \verb+10+, \verb+101+.
          \item O conjunto das palavras em que as posi\c c\~oes \'{\i}mpares s\'o
                t\^em \verb+1+'s.
                Exemplos: $\lambda$, \verb+101+, \verb+111+, \verb+1010111011+.
          \item O conjunto das palavras de tamanho m\'ultiplo de 3 terminadas em
                \verb+11+.
        \end{list}

 \item Seja a gram\'atica $G=(\{P,A,B,D\},\{\verb+0+,\verb+1+,\#\},R,P)$, onde $R$ \'e:
       \begin{enumerate}
        \item[\ ] $P \,\,\rightarrow\,\, A \# B$
        \item[\ ] $A \,\,\rightarrow\,\, D D A \,\,|\,\, \lambda$
        \item[\ ] $B \,\,\rightarrow\,\, B \verb+1+ \,\,|\,\, \lambda$
        \item[\ ] $D \,\,\rightarrow\,\, \verb+0+ \,\,|\,\, \verb+1+$
       \end{enumerate}
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Que linguagem \'e gerada por $G$?
        \item Construa uma gram\'atica que gere $L(G)$, por\'em sem usar regra
              com o lado direito igual a $\lambda$.
        \item Para uma das gram\'aticas, determine quantos passos s\~ao necess\'arios
              para derivar uma palavra de tamanho $n$.
       \end{list}

 \item Construa aut\^omatos finitos determin\'{\i}sticos que reconhe\c cam:
         \begin{list}{(\alph{conta})}{\usecounter{conta}}
          \item $\{\verb+0+\}$
          \item O conjunto das palavras sobre $\{\verb+0+,\verb+1+\}$ de tamanho
                \'{\i}mpar e terminadas em \verb+1+.
          \item $\{\verb+b+,\verb+ab+\}^*\{\verb+ba+,\verb+a+\}^*$
          \item $\{w\in\{\verb+0+,\verb+1+\}^*\,\,|\,\, |w| \mbox{ mod } 3=0 
                \mbox{ e } w \mbox{ n\~ao cont\'em }\verb+00+\}$
         \end{list}

 \item Sejam as linguagens:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item $\{\verb+0+^m\verb+1+\verb+0+^n\,\,|\,\, m<n\}$
        \item $\{\verb+0+^n\verb+00+^n\,\,|\,\, n\in\mbox{\bf N}\}$
       \end{list}
       Mostre que a primeira n\~ao pode ser reconhecida por AFD, e que a
       segunda pode.

 \item Sim ou n\~ao? Por que?
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Se a linguagem $L$ n\~ao pode ser reconhecida por AFD e $L\subseteq X$,
              $X$ n\~ao pode ser reconhecida por AFD.
        \item Para qualquer AFD $M$ existe um AFD $N$ tal que $L(M)=L(N)$ e $N$
              tem apenas 1 estado final.
       \end{list}

\end{enumerate}
\end{document}

