\documentclass[11pt,a4paper]{article}
\usepackage[portuguese]{babel}
\usepackage[latin1]{inputenc}
\usepackage{vector}
\usepackage{fullpage}
\usepackage{amssymb}
\usepackage{amstext}

\begin{document}

\selectlanguage{portuguese}

\begin{tabular*}{\linewidth}{l@{\extracolsep{\fill}}r}
  Graduação em Ciência da Computação           & DCC/ICEx/UFMG \\
  \textit{Fundamentos da Teoria da Computação} & $1^{\uvec{o}}$ semestre de 2003\\
  Professor: Newton José Vieira                & \\
  email: \texttt{nvieira@dcc.ufmg.br}          & \\
  \textbf{Quarto Trabalho Prático}             & Entrega: 18/08/2003
\end{tabular*}

\bigskip

\noindent {\bf Observações:}
\begin{itemize}
\item O trabalho deverá ser feito por 1 ou 2 alunos. Em hipótese alguma serão aceitos grupos com mais de 2 alunos.
\item Deverá ser entregue um relatório completo em papel.
\item O trabalho deverá ser entregue todo de uma vez. Ou seja, após a entrega, não será aceita complementação {\bf em hipótese alguma}.
\item Se o trabalho for entregue com $n$ dias de atraso, {\bf qualquer que seja o motivo}, serão descontados $2^{n}$ pontos.
\end{itemize}

\section*{Lista de exercícios: Máquinas de Turing}

\begin{enumerate}
\item Construa MT's para as seguintes linguagens:
  \begin{enumerate}
  \item $\left\{0^{2n} \; | \; n \geqslant 0\right\}$.
  \item $\left\{0^{2^{n}} \; | \; n \geqslant 0\right\}$.
  \item $\left\{0^{n} 1^{n} \; | \; n \geqslant 0\right\}$.
  \item $\left\{0^{n} 1^{n} 2^{n} \; | \; n \geqslant 0\right\}$.
  \end{enumerate}
\item Construa MT que:
  \begin{enumerate}
  \item Subtraia $1$ a um número inteiro positivo escrito na fita (se este número for zero, o resultado é zero).
  \item Some $1$ a um número inteiro positivo escrito na fita.
  \end{enumerate}
\item Verifique que uma MT que só pode movimentar o cabeçote a direita ou deixá-lo imóvel não tem o mesmo poder computacional que uma MT padrão. Este tipo de MT é equivalente a um AFD ou é mais poderoso?
\item Verifique que uma MT pode reconhecer palíndromo no alfabeto $\Sigma = \left\{0,1\right\}$:
  \begin{enumerate}
  \item Em tempo linear se a máquina tem duas fitas.
  \item Em tempo quadrático se a máquina tem uma fita só.
  \end{enumerate}
\item Escreva MT's não determinísticas de duas fitas que reconheçam as linguagens:
  \begin{enumerate}
  \item $\left\{xx \; | \; x \in \left\{0,1\right\}^{*}\right\}$.
  \item $\left\{xx^{R}y \; | \; x,y \in \left\{0,1\right\}^{*} \text{ e } |x| > |y| \right\}$.
  \end{enumerate}
%\item Nós chamamos um $k-$APD um autômato com pilha determinístico com $k$ pilhas. Um $0-$APD é um AFD. Um $1-$APD é um APD clássico.
%  \begin{enumerate}
%  \item Provar que o poder computacional de um $2-$APD é maior que o de um $1-$APD.
%  \item Provar que o poder computacional de um $3-$APD não é maior que o de um $2-$APD.
%  \end{enumerate}
\item Seja uma MT determinística com uma fita ilimitada em duas dimensões. O cabeçote pode se movimentar nas direções $\leftarrow$ e $\rightarrow$, mas também nas direções $\uparrow$ e $\downarrow$. A posição inicial do cabeçote é em baixo à esquerda, e a palavra de entrada está escrita horizontalmente à direita da posição inicial do cabeçote. Definir formalmente uma tal MT.
\end{enumerate}

\section*{A ser entregues}

Vocês devem entregar, no papel, as respostas às perguntas.

Todos os comentários relacionados com este trabalho (dificuldade, quantidade de trabalho, etc.) são bem-vindos.

\end{document}

% LocalWords:  complementação Turing MT cabeçote palíndromo MT's APD
