\documentclass[12pt]{article}

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc} % isso é quase redundante
%\usepackage{textcomp}
%\usepackage[T1]{fontenc}
%----------------------------

\setlength{\topmargin}{-.5in}
\setlength{\textheight}{9in}
\setlength{\textwidth}{6.3in}
\setlength{\oddsidemargin}{-.125in}
\setlength{\evensidemargin}{-.125in}

\usepackage{hyperref}
\usepackage{xspace}
\usepackage{pifont}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{color}
\usepackage{fancybox}
\usepackage{mathrsfs}
\usepackage{stix}
\usepackage{tikz}
\usetikzlibrary{automata}

\usepackage[useregional=numeric]{datetime2}


\renewcommand{\SS}[1]{{\scriptsize #1}}


\pagestyle{empty}
\newcommand{\N}{{\tt I\kern-.2em N \relax}}      % N        |N
\def\pule{\vspace{0.2cm}}
\def\pulao{\vspace{0.5cm}}
\def\pulaozao{\vspace{1cm}}
\def\ni{\noindent}

\newcommand{\Si}{\ensuremath{\Sigma}\xspace}
\newcommand{\Sis}{\ensuremath{\Sigma^*}\xspace}
\newcommand{\serio}{\ding{98}\xspace}
\newcommand{\obr}{\ding{42}\xspace}
\newcommand{\LP}{\textbf{L\&P}\xspace}
\newcommand{\SI}{\textbf{Sipser}\xspace}
\newcommand{\RI}{\textbf{Rich}\xspace}
\newcommand{\conj}[2]{\ensuremath{\{#1\,|\;#2\}}}
\newcommand{\cala}{\ensuremath{\mathscr{A}}\xspace}
\newcommand{\calb}{\ensuremath{\mathscr{B}}\xspace}
\newcommand{\cele}{\ensuremath{\mathscr{L}}\xspace}
\newcommand{\cals}{\mathscr{S}}

\begin{document}

\begin{center}
\large \bf
MAC 414  --  Autômatos, Computabilidade e Complexidade\\
Exercícios\\
\DTMtoday\ --- \DTMcurrenttime



\end{center}
Ao provar algo, use livremente os resultados vistos em aula ou em exercícios.
Ao apresentar um exemplo, \textbf{mostre} que ele tem a propriedade
 que você quer exemplificar. 

 Com relação à
 \href{https://www.ime.usp.br/~am/414-20/refbib.html}{bibliografia}, a
 notação e terminologia nem sempre bate com a do curso, faz parte dos
 exercícios entender a notação do livro, mas escrever na do curso.
 
 \LP é o livro [1], \SI é o livro [5] (original), \RI é o livro [8].
 Se o exercício aparece em \textbf{negrito} é porque é especialmente
 interessante.

 Muitas dessas questões foram retiradas de listas de edições
 anteriores do curso, e o texto pode parecer peculiar. Assim, podem
 haver repetições, e a ordem dos exercícios não correspondem à
 sequência da matéria no curso. Alguns podem ter sido feitos em aula.

\noindent \textbf{A) Autômatos}
\begin{enumerate}
    \item Sejam  \(A,B\subseteq\Sigma^\ast\), e considere a equação: \(X=AX+B\),
  na linguagem incógnita \(X\).  Seja \(L=A^\ast B\). Mostre:
  \begin{enumerate}
      \item Toda solução da equação contem \(L\).\\
    {\small\textsl{Sug.: mostre que \(A^nB\subseteq X\), para todo \(n\geq 0\).}}
      \item \(L\) é uma solução da equação.
      \item Se \(\lambda\not\in A\), então \(L\) é a única solução da equação.\\
    {\small\textsl{Sug.: suponha que \(X\neq L\) é uma solução.  Como \(L\subseteq
        X\), deve existir alguma palavra \(x\in X-L\). Escolha uma tal palavra, de
        comprimento mínimo; como \(X\) é solução da equação, \(x\) deve ter uma
        fatoração de um certo tipo.  Use isso para chegar a uma contradição.}}
      \item Dê um exemplo de equação  \(X=AX+B\) que tenha infinitas soluções
    distintas. 
  \end{enumerate}

    \item Encontre uma expressão regular para cada linguagem abaixo sobre o
  alfabeto \(\Sigma=\{a,b\}\):
  \begin{enumerate}
      \item \(\{x\in \Sigma^\ast \mid |x|_a \quad\mbox{é par, ou}\quad |x|_b
    \quad\mbox{é par}\}\).
      \item \(\{x\in \Sigma^\ast \mid x \quad\mbox{não contem o fator}\quad
    aa\}\).
  \end{enumerate}
  Tente demonstrar que cada expressão é correta.

    \item Para  \(A,B\subseteq\Sigma^\ast\) definimos:
  \[
    \begin{array}[c]{l}
      A^{-1}B = \{t\in\Sigma^\ast | \mbox{existe $s\in A$ tal que $st\in B$}\}\\
      BA^{-1} = \{t\in\Sigma^\ast | \mbox{existe $s\in A$ tal que $ts\in B$}\}
    \end{array}\]
  Mostre que:
  \begin{enumerate}
      \item \((AC^{-1})B^{-1} = A(BC)^{-1}\).
      \item \((A^{-1}B)C^{-1} = A^{-1}(BC^{-1})\).
  \end{enumerate}
  
    \item Substituição, uma generalização da noção de morfismo.  Dado um conjunto
  \(A\), denotamos por \(2^A\) a família de todos os subconjuntos de \(A\)
  (alguns preferem a notação \(\mathscr{P}(A)\)).  Assim, se \(\Gamma\) é um
  alfabeto, \(2^{\Gamma^\ast}\) é a família de todas as linguagens sobre
  \(\Gamma\), e é um monóide com a operação produto de linguagens.  Assim,
  dada uma função \(s:\Sigma\rightarrow 2^{\Gamma^\ast}\), ela se estende
  naturalmente a um morfismo \(s:\Sigma^\ast\rightarrow 2^{\Gamma^\ast}\).
  Vamos estender \(s\) ainda mais, ao domínio \(2^{\Sigma^\ast}\) por
  \(s(L)=\cup_{x\in L} s(x)\), para cada linguagem \(L\) sobre \(\Sigma\).
  Esse tipo de função é chamado uma \emph{substituição}.  Mostre que, dada uma
  tal substituição:
  \begin{enumerate}
      \item Para quaisquer linguagens \(A, B\), \(s(A\cup B)=s(A)\cup s(B)\),
    \(s(AB)=s(A)s(B)\), \(s(A^\ast)=s(A)^\ast\).
      \item Se para cada letra \(\sigma\in\Sigma\), \(s(\sigma)\) é regular, então,
    para cada linguagem regular \(L\), \(s(L)\) é regular.
      \item Se \(\alpha, \beta\) são expressões regulares equivalentes, então
    substituindo-se cada letra por uma linguagem resultam duas expressões que
    ainda denotam a mesma linguagem.  Assim, por exemplo:

    É mais ou menos fácil mostrar que \((aab)^+=a(aba)^\ast ab\). Daí segue
    que para \emph{quaisquer linguagens} \(A,B\), \((AAB)^+=A(ABA)^\ast AB\).
  \end{enumerate}

    \item Para este exercício, estamos interessados em funções realizadas
  por programas, ou seja, \(f\) pode ser declarada como:\\
  \hspace{5cm}  \textbf{string} \(f\)(\textbf{int} n); \\
  Aqui, suponho que a linguagem de programação tem os tipos:\\
  \ \ \ \ \textbf{string} --- palavras em \Sis\\
  \ \ \ \ \textbf{int} --- inteiros de tamanho arbitrário (qualquer número de
  dígitos)\\
  e que a sintaxe permite exprimir convenientemente concatenação, acesso a
  caracteres, e operações aritméticas.  Fora isso , a sintaxe pode ser um
  misto de C, Pascal, Java, Perl, a gosto do freguês.  Dizemos que \(f\)
  \emph{enumera} \(L\subseteq\Sis\) se \(L\) é a imagem de \(f\).  Trocando em
  miúdos, isto quer dizer que (a) para todo \(i\in\N\), \(f(i)\in L\), e (b)
  para todo \(x\in L\), existe \(i\) tal que \(f(i)=x\).  Note que \(f\) não
  precisa ser injetora, ou seja o mesmo \(x\) pode ser imagem de vários \(i\).

  Mostre como, a partir de uma descrição de um autômato determinístico
  \cala, produzir uma função que enumera
  \(L(\cala)\).  Se quiser caprichar, faça isso para um
  autômato não determinístico.  Escreva a função no mais alto nível possível;
  defina outras funções (como você está acostumado a fazer quando programa)
  para fazer detalhes.

  Note que ninguém vai compilar ou testar seu programa.  O importante é
  explicar como ele funciona, ou num comentário por fora ou em comentários
  embutidos no código.
  
  \textbf{Parte extra}:
  Mostre como construir uma função enumeradora para qualquer linguagem regular
  exceto \(\emptyset\), a partir de uma expressão regular.  Roteiro:
  \begin{enumerate}
      \item Construa listadores para as linguagens que consistem de uma letra e
    para a linguagem \(\lambda\).
      \item Mostre como, dadas funções enumeradoras para \(L_1, L_2\), construir
    uma função enumeradora para \(L_1\cup L_2\).  Acho que usando apontadores
    para funções fica mais fácil trabalhar.  Enfim, este é facil.
      \item Mostre como, dadas funções enumeradoras para \(L_1, L_2\), construir
    uma função enumeradora para \(L_1 L_2\).  Este é difícil, mas acho que
    muitos de vocês, se tentarem, fazem.
      \item Mostre como, dada uma função enumeradora para \(L\), construir uma
    função enumeradora para \(L^\ast\).  Esta é \textsl{bem difícil}.  Se
    alguém fizer isso bem feito e me convencer que está certo, pode me
    convencer a ganhar algum bônus ou dispensa de outra lista.
  \end{enumerate}
  
    \item Construa um autômato sobre o alfabeto \(\{0,1\}\) que reconhece as
  palavras que são representações binárias de números divisíveis por 3 (com
  qualquer quantidade de zeros à esquerda).
  
  {\footnotesize Sug.: Se \((x)_2=n\) então \((x\sigma)_2=2n+\sigma\) e vale a
    relação \newline
    {\phantom a} \hspace{4em}
    \((2n+\sigma) \bmod 3 = (2n\bmod 3)+\sigma\bmod 3\).} 

    \item Considere o autômato dado por
  \[
    \begin{array}{c}
      K=\{q_0,q_1,q_2,q_3\}, \Sigma=\{a,b\}, s=q_0, F=\{q_1,q_3\}\\
      \delta(q_i,a)=q_j, \quad \mbox{onde} \quad j\equiv i+1\bmod 4 \\
      \delta(q_i,b)=q_j, \quad \mbox{onde} \quad j\equiv i-1\bmod 4

    \end{array}
  \]
  \begin{enumerate}
      \item Desenhe seu diagrama, e use um dos métodos dados em aula para encontrar
    uma expressão regular para a linguagem que ele reconhece.
      \item Prove que ele reconhece a linguagem \((a+b)(aa+ab+ba+bb)^\ast\).
  \end{enumerate}

    \item Um \emph{semiautômato} é uma quádrupla \(\cals=(K,\Sigma,\delta,s)\),
  cujas componentes têm o mesmo significado que para um autômato.  Assim, se
  \(F\subseteq K\), \(\cala=(\cals,F)\) é um autômato, \emph{derivado}
  de $\cals$.
  \begin{enumerate}
      \item Mostre que a família de linguagens reconhecidas pelos autômatos
    derivados de um semiautômato $\cals$ forma uma álgebra booleana, com as
    operações de conjuntos.
      \item Dados semiautômatos \(\cals_i=(K_i,\Sigma,\delta_i,s_i), i=1,2\),
    sobre o mesmo alfabeto, seu \emph{produto} \(\cals_1\times\cals_2\) é
    definido por:
    \[
      \begin{array}{c}
        K=K_1\times K_2, \qquad s=(s_1,s_2),\\
        \delta\left((p_1,p_2),\sigma\right)=
        \left(\delta_1(p_1,\sigma),\delta_2(p_2,\sigma)\right)
      \end{array}
    \]
    Mostre que para toda palavra $x$ vale que \newline
    {\phantom a} \hspace{4em} \(\delta\left((p_1,p_2),x\right)=
    \left(\delta_1(p_1,\sigma),\delta_2(p_2,x)\right)\). 
      \item Como no ítem anterior, seja \(F\subseteq K_1\).  Mostre que
    \(L((\cals_1,F)) = L((\cals_1\times\cals_2,F\times K_2))\). 
      \item Juntando os três ítens anteriores, mostre que a união e a interseção
    de linguagens reconhecíveis é reconhecível.

    {\footnotesize Sug.: dados dois autômatos, suas duas linguagens são
      reconhecidas por derivados do semiautômato produto dos
      semiautômatos correspondentes aos autômatos dados.}
  \end{enumerate}

  
    \item Suponha que, na sua linguagem orientada a objetos predileta, esteja
  definida a classe \texttt{Autômato}, com três métodos:
  \begin{itemize}
      \item \texttt{inicial} --- devolve o estado inicial,
      \item \texttt{delta} --- função, com argumentos \texttt{estado, letra},
    devolve um estado (implementa a função \(\delta\)),
      \item \texttt{final} --- função booleana, tem um estado como argumento,
    devolve 1 se e só se o argumento é um estado final.
  \end{itemize}
  Vamos supor que  \texttt{estado} e \texttt{letra} são tipos já existentes.

  
    \item Construa um reconhecedor genérico para esta classe, ou seja uma função
  booleana com dois argumentos, um autômato \cala e uma palavra \(x\), e que
  devolve 1 se e só se \(x\in L(\cala)\).  A função deve funcionar em
  tempo linear em \(\mid x\mid\).
    \item Construa funções booleanas \texttt{Uniao}, \texttt{Inter}, ambas com
  três argumentos, autômatos \(A_1, A_2\) e uma palavra \(x\), e que
  funcionam como reconhecedores para \(L(\cala_1\cup \cala_2)\) e
  \(L(\cala_1\cap \cala_2)\), respectivamente.  Use o exercício anterior
  para ter uma idéia como fazer isso.  Existem duas possibilidades:
  \begin{enumerate}
      \item Construir um novo autômato para a união e um para a interseção, e
    aplicar o reconhecedor da primeira parte.  Isso provavelmente vai exigir
    alguma mudança na descrição do objeto, para se poder por a mào no
    conjunto de estados.
      \item Construir os reconhecedores \textbf{sem} construir os autômatos.
    Isso dá para fazer, de uma forma eficiente, e é a forma certa de se
    entender o produto direto: um processamento paralelo nos dois
    autômatos. 
  \end{enumerate}
    \item Considere o autômato dado por
  \[
    \begin{array}{c}
      K=\{q_0,q_1,q_2,q_3\}, \Sigma=\{a,b\}, s=q_0, F=\{q_1,q_3\}\\
      \delta(q_i,a)=q_j, \quad \mbox{onde} \quad j\equiv i+1\bmod 4 \\
      \delta(q_i,b)=q_j, \quad \mbox{onde} \quad j\equiv i-1\bmod 4

    \end{array}
  \]
  \begin{enumerate}
      \item Desenhe seu diagrama, e use um dos métodos dados em aula para encontrar
    uma expressão regular para a linguagem que ele reconhece.
      \item Prove que ele reconhece a linguagem \((a+b)(aa+ab+ba+bb)^\ast\).
  \end{enumerate}

    \item Descreva algoritmos para:
  \begin{enumerate}
      \item Dado um autômato determinístico, decidir se a linguagem que ele
    reconhece é não vazia.
      \item Dadas duas expressões regulares, decidir se elas descrevem a mesma
    linguagem.
  \end{enumerate}
  \textbf{Note bem:} Na descrição dos algoritmos acima, use livremente os
  algoritmos vistos em aula, bem como algoritmos bem conhecidos sobre grafos,
  etc.  Por exemplo, um algoritmo para descobrir se um autômato não
  determinístico aceita uma palavra da forma \(a^n\) seria: \emph{faça uma
    busca em profundidade no grafo do autômato a partir dos estados iniciais,
    usando só arestas com rótulo em \(a^\ast\); responda sim se e só se algum
    estado final for atingido.}

  Os algoritmos têm que estar corretos, mas não precisam ser eficientes.

    \item Seja $\Sigma$ um alfabeto, e sejam $A,B\subseteq\Sigma^*$.  Defina
  \[
    \begin{split}
      L_{A,B}=\{x\in\Sigma^*|\,\text{nenhuma palavra de $A$ é segmento de $x$ e}\\
      \text{toda palavra de $B$ é segmento de $x$}\}.
    \end{split}
  \]
  Mostre que se $A$ é regular e $B$ é finita, então $L_{A,B}$ é regular. (Obs:
  esta questão tem uma solução muito simples - baseada na teoria, claro.)

    \item Lembre que uma \emph{subpalavra} de uma palavra \(x\) é qualquer palavra
  que se pode obter de \(x\) apagando-se algumas letras.  Mais formalmente,
  \(y\) é subpalavra de \(x\) se existe uma fatoração \(x=w_0y_1w_1y_2\ldots
  y_nw_n\) tal que \(y=y_1y_2\ldots y_n\).  Dada uma linguagem \(L\), definimos
  a linguagem
  \[L^\dag=\{x\in\Sigma^\ast \mid \mbox{alguma subpalavra de \(x\)
      está em \(L\)}\}.\]
  Por exemplo, se \(\lambda\in L\), então
  \(L^\dag=\Sigma^\ast\).  Mostre como modificar um autômato não
  determinístico \cala obtendo outro que reconhece
  \(L(\cala)^\dag\).
  

    \item Considere autômatos determinísticos \(\cala=(Q,\Si,\delta,s,F),
  \cala'=(Q',\Si,\delta',s',F')\).  Uma função \(f:Q\rightarrow Q'\)
  é uma \emph{simulação} se:
  \begin{itemize}
      \item [ ] \(f(s) = s'\) e
      \item [ ] para todo \(\sigma\in\Si, q\in Q\), \(f(\delta(q,\sigma)) =
    \delta'(f(q),\sigma)\). 
  \end{itemize}
  \begin{enumerate}
      \item Mostre que para toda palavra \(x\in\Sigma^\ast\), \(f(\delta(s,x)) =
    \delta'(s',x)\).
      \item A simulação é \emph{exata} se vale: \(f(q)\in F' \Leftrightarrow q\in F\).
    Mostre que quando existe uma simulação é exata,
    \(L(\cala)=L(\cala')\). 
  \end{enumerate}


    \item Dê exemplos de linguagens não-vazias \(A\), \(B\) e \(C\) sobre
  \(\Sigma = \{a, b \}\) tais que
  \begin{enumerate}
      \item \(AB = AC\), mas \(B \neq C\)
      \item \(A(B \cap C) \neq AB \cap AC\)
  \end{enumerate}
  Uma das inclusões \(A(B \cap C) \subseteq AB \cap AC\) ou \(AB \cap AC
  \subseteq A(B \cap C)\) é sempre válida.\\
  Prove-a.
  
    \item Seja \(L = \left\{x \in \left\{0, 1\right\}^* : |x|_0 \neq |x|_1
  \right\}\).  Prove que
  \begin{enumerate}
      \item \(L^* = \{0, 1\}^*\)
      \item \(\overline{L}^{\;*}=\overline{L}.\)  Obs.:  \(\overline{L} =
    \Sis\backslash L\), é o complemento de \(L\).
  \end{enumerate}


    \item Sejam \(A\), \(B\) e \(C\) linguagens sobre \Si.  Prove que:
  \begin{enumerate}
      \item  Se \(A \subseteq B\) então \(AC \subseteq BC\) e \(CA
    \subseteq CB\).  Dê infinitos exemplos de linguagens não-vazias \(A\),
    \(B\) e \(C\) tais que \(A\subset B\) e \(AC=BC\).
      \item  $(A \cup B)C = AC \cup BC$
      \item  Se \(A \subseteq B\) então \( A^* \subseteq B^*\).
      \item  Se \(A \subseteq C^*\) e \(B \subseteq C^*\) então \(AB
    \subseteq C^*\).
      \item \((A \cup B)^* = (B^* A)^* B^*\)
  \end{enumerate}


    \item  Se \(\sigma\in\Si\), então, para \(x\in\Sis\), denota-se por
  \(|x|_\sigma\) o número de ocorrências de \(\sigma\) em \(x\); isto é, 
  \(|x|_\sigma= \left|\left\{i\mid x_i=\sigma\right\}\right|\). Mostre:
  \begin{enumerate}
      \item \(|xy|_\sigma=|x|_\sigma+|y|_\sigma\)
      \item \(|x|={\displaystyle\sum_{\sigma\in\Si}} |x|_\sigma\)
  \end{enumerate}


    \item Mostre que a linguagem sobre  \(\Sigma = \{a, b \}\) descrita por
  \[
    \{x: |x|_a = |x|_b\} + (a+b)^*(aa+bb)(a+b)^*
  \]
  é regular; ou seja, encontre uma expressão regular para ela e prove que
  está correta. {\footnotesize Por outro lado, \(\{x: |x|_a = |x|_b\} +
    (a+b)^*(aaa+bbb)(a+b)^*\) não é regular, mas tem muito chão pela frente
    antes de provar isso.}
  
    \item Para um inteiro \(k\geq 2\), considere o alfabeto
  \(\Si_k=\{0,1,\ldots,k-1\}\) dos dígitos usados para escrever em base \(k\).
  Para \(x\in\Sis_k\), seja \([x]_k\) o inteiro que \(x\) representa em base
  \(k\).  Ou seja, se \(x=x_0x_1\ldots x_m\) (note a indexação), então
  \([x]_k=\sum_{i=0}^m x_i k^{m-i}\).
  Para \(n\geq 2, i\in \Si_k\), dê um AD para as linguagens:
  \begin{enumerate}
      \item \(L_{k,n,i}=\{x\in\Sis_k: [x]_k \equiv i \bmod n\}\).  Ou seja, como
    decidir a classe de \([x]_k \bmod n\) com uma varredura dos dígitos da
    esquerda para a direita.
      \item O reverso de \(L_{k,n,i}\). Ou seja, como decidir a classe de
    \([x]_k \bmod n\) com uma varredura dos dígitos da
    direita para a esquerda.
      \item [Obs:] isso parece muito mais difícil do que é.  Experimente com
    \(n=3,4\), \(i=0,1,2\) e valores pequenos de \(k\).  Mesmo \(k=2\) já
    é interessante.
  \end{enumerate}
    \item Construa autômatos determinísticos que reconheçam as seguintes
  linguagens sobre o alfabeto \(\Si=\{a,b\}\), e dê uma expressão regular
  para cada uma delas:
  \begin{enumerate}
      \item Palavras em que cada \(a\) é imediatamente precedido por um \(b\).
      \item Palavras que contém o segmento \(abab\).
      \item Palavras em que o número de \(b\)'s entre cada par de ocorrências de
    \(a\) é par
  \end{enumerate}

    \item Construa o AD reduzido que reconhece
  \[
    \biggl(b^*\Bigl(\left(a+b\right)\left(ab^*a+b\right)\Bigr)^*(a+b)ab^*+b^*\biggr)
    \biggl(a\Bigl(\left(a+b\right)b\Bigl)^*(a+b)a+b\biggl)^*
  \]
  Use os algoritmos vistos em aula, colocando detalhe suficiente para
  mostrar que você conhece os algoritmos, mas não todos os detalhes.  Pode
  também curto-circuitar partes da construção do AND a partir da ER, mas
  cuidado porque isso pode levar a erro.
    \item Mostre que \(\{a^nb^pa^m\,|\, n+m\geq 100, p\,\mbox{é primo}\} \) não é regular.
    \item Mostre que a linguagem das expressões regulares sobre o alfabeto
  \(\{a,b\}\), vista como linguagem sobre o alfabeto
  \(\{a,b,+,{}^*,(,),\emptyset\}\), não é regular.

    \item Dada uma linguagem \(L\), definem-se as linguagens
  \(\mbox{Pref}(L)=\{x\,|\,\exists y\,\,\mbox{tal que}\,\, xy\in L\}\) e
  \(\mbox{Suf}(L)=\{x\,|\,\exists y\,\,\mbox{tal que}\,\, yx\in L\}\).  Mostre que
  se \(L\) é regular, então essas duas também o são, de dois jeitos diferentes:
  \begin{enumerate}
      \item Mostre como, dada uma expressão regular para \(L\), obter ERs para
    \(\mbox{Pref}(L)\) e \(\mbox{Suf}(L)\).
      \item Mostre como, dada um autômato para \(L\), obter autômatos para
    \(\mbox{Pref}(L)\) e \(\mbox{Suf}(L)\).
  \end{enumerate}
  Essas construções devem ser diretas, sem usar o Teorema de Kleene.  No caso
  de autômatos, não é necessário preservar determinismo.

  
    \item Um \emph{identificador} em C é uma palavra não vazia composta de letras
  (sem acento) maiúsculas ou minúsculas, dígitos, o sublinhado \texttt{\_} \ ,
  e não pode começar por dígito.  Mostre que o conjunto de identificadores é
  uma linguagem regular.  Crie seu próprio açúcar sintático, se achar
  necessário.

    \item Dê uma expressão regular para cada linguagem abaixo, onde \(\Si=\{a,b\}\):
  \begin{enumerate}
      \item palavras que contém ambas as subpalavras \(aa\) e \(aba\).
      \item palavras que não contém letras consecutivas iguais.
      \item palavras que não terminam em \(ba\).
      \item palavras que não contém a subpalavra \(bba\).
      \item palavras com no máximo uma ocorrência de \(aa\) e no máximo uma
    ocorrência de \(bb\) (por exemplo, \(ababbabaaba\) está na linguagem).
      \item palavras \(w\) tais que existe \(z\) tal que \(wz\) está na
    linguagem do item anterior.
  \end{enumerate}

    \item Para cada linguagem da questão anterior, dê um autômato determinístico
  que a reconheça.

    \item Uma palavra \(u\) é uma \emph{intercalação} das palavras \(x\) e \(y\),
  se existe uma fatoração \(u=u_1v_1u_2v_2\cdots u_nv_n\) tal que
  \(x=u_1u_2\ldots u_n\) \(y=v_1v_2\ldots v_n\).  Por exemplo, as
  intercalações de \(\mathbf{ba}\) e \(abc\) são
  \(\mathbf{b}\mathbf{a}abc,\mathbf{b}ab\mathbf{a}c,\mathbf{b}abc\mathbf{a},
  a\mathbf{b}\mathbf{a}bc,a\mathbf{b}b\mathbf{a}c,ab\mathbf{b}c\mathbf{a},
  abc\mathbf{b}\mathbf{a}\).  O \emph{embaralhamento} de duas linguagens \(L\)
  e \(H\) é \[L\shuffle H = \{u\in\Sis\,:\,  \mbox{\(u\) é uma intercalação de
      algum \(x\in L\) e algum \(y\in H\)}\}.\]

  Mostre que se \(L\) e \(H\) são regulares, \(L\shuffle H\) também é.


    \item Dadas linguagens \(L\) e \(H\), definimos a linguagem \(\frac{L}{H} =
  \{x\in\Sis\,:\,\mbox{existem\ }u,v\in H \mbox{\ tais que\ } uxv\in L\}.\)
  Mostre que se \(L\) é regular, então, para qualquer linguagem \(H\) (pode
  nem ser regular), \(\frac{L}{H}\) é regular.


    \item Escreva uma expressão regular para o complemento de \(L(\cala)\), onde
  \cala é o AND abaixo, e \(\Si=\{0,1\}\).  Explique como chegou nela.
  \begin{center}
    \begin{tikzpicture}[scale=0.5,shorten >=1pt,node
      distance=3cm,auto, initial text=,>=stealth]
      \node[state,initial,accepting] (q_0) {$0$};
      \node[state] (q_1)[right of=q_0] {$1$};
      \node[state, accepting] (q_2)[right of=q_1]{$2$};
      \path[->]
      (q_0) edge  node {$0$} (q_1)
      (q_0) edge[loop above] node {$1$} ()
      (q_1) edge  node {$1$} (q_2)
      (q_2) edge[loop above]  node {$0$} ();
    \end{tikzpicture}
  \end{center}


    \item \emph{Joquenpô}, também conhecido como ``Pedra, Papel e Tesoura'', é um
  jogo para dois jogadores.  Uma jogada consiste de os dois jogadores
  exibirem um gesto que representa um dos três objetos.  Se os dois jogadores
  fazem a mesma escolha, a jogada empatou.  Senão, o vencedor da jogada é
  determinado pelas regras
  \begin{itemize}
      \item Tesoura ganha de Papel
      \item Papel ganha de Pedra
      \item Pedra ganha de Tesoura
  \end{itemize}
  Mais detalhes a uma gugada de distância (ou Wikipedia direto).

  Num torneio modelo \texttt{414} de joquenpô, os jogadores jogam sucessivamente, e o
  primeiro que ganhar duas jogadas vence.  Seu objetivo é inventar uma
  codificação das jogadas tal que uma sequência delas possa ser processada por
  um semi-autômato que informa quem ganhou, no momento em que ganhou.

  Mais precisamente:
  \begin{itemize}
      \item Cada letra do alfabeto deve indicar um resultado possível de jogada
      \item Devem existir dois conjuntos (disjuntos) de estados finais, \(F_1,
    F_2\), tais que, ao chegar em \(F_i\) significa que o jogador \(i\) ganhou.
  \end{itemize}

  Os mais corajosos podem tentar descrever um semi-autômato para
  \texttt{414++}, em que é preciso ganhar três jogadas para vencer o torneio.

    \item Para o autômato abaixo, tente descrever a linguagem que ele
  aceita numa frase em português matemático.  Algo como ``todas as
  palavras tais que...''
  \begin{figure}[h]
    \centering
    \begin{tikzpicture}[node distance=3cm,auto,initial text=]
      \node[state,initial] (q_1) {$1$};

      \node[state,accepting] (q_2) [right of=q_1] {$2$};

      \node[state,accepting] (q_3) [right of=q_2] {$3$};

      \node[state] (q_4) [below of=q_1] {$4$};

      \node[state,accepting] (q_5) [right of=q_4] {$5$};

      \node[state] (q_6) [right of=q_5] {$6$};

      \path[->]

      (q_1) edge  node {$b$} (q_2)

      (q_1) edge [bend right] node {$a$} (q_4)

      (q_2) edge  node {$a$} (q_3)

      (q_2) edge  [loop above] node {$b$} ()

      (q_3) edge [bend right] node {$a$} (q_6)

      (q_3) edge  node {$b$} (q_5)

      (q_4) edge [bend right] node {$a$} (q_1)

      (q_4) edge  node {$b$} (q_5)

      (q_6) edge [bend right] node {$a$} (q_3)

      (q_5) edge [loop below] node {$1,2$} ();
    \end{tikzpicture}
  \end{figure}


    \item Considere o seguinte algoritmo, dado um AD \cala:
  \begin{itemize}
      \item Faça duas vezes:
    \begin{enumerate}
        \item Reverta \cala (como se fosse um AND).
        \item Aplique a construção dos subconjuntos, tomando só a
      parte acessível.
    \end{enumerate}
      \item Devolva o AD resultante.
  \end{itemize}
  Claro que o autômato \cala' devolvido pelo algoritmo reconhece a mesma
  linguagem que \cala.
  \begin{enumerate}
      \item Mostre que esse autômato tem no máximo tantos estados quanto \cala.
      \item Mostre que repetindo essa construção com \cala' resulta
    num autômato isomorfo a \cala'.
      \item  Aplique o algoritmo no autômato abaixo (devolva simplesmente
    a sucessão de desenhos dos autômatos que obtiver, com os estados
    rotulados de um modo que seja fácil de acompanhar a construção):
    \begin{figure}[h]
      \centering
      \begin{tikzpicture}[node distance=3cm,auto,initial text=,style=thick]
        % \pgfsetarrowsend{latex}
        
        \node[state,initial] (q_1) {$1$};

        \node[state] (q_2) [right of=q_1] {$2$};

        \node[state,accepting] (q_3) [right of=q_2] {$3$};

        \node[state] (q_4) [right of=q_3] {$4$};

        \node[state,accepting] (q_5) [below of=q_1] {$5$};

        \node[state,accepting] (q_6) [right of=q_5] {$6$};

        \node[state,accepting] (q_7) [right of=q_6] {$7$};

        \node[state,accepting] (q_8) [right of=q_7] {$8$};

        \path[->]

        (q_1) edge [bend left] node {$b$} (q_2)

        (q_1) edge  node [left] {$a$} (q_6)

        (q_2) edge  node {$a$} (q_3)

        (q_2) edge  [bend left] node  [above] {$b$} (q_1)

        (q_3) edge  node {$a$} (q_7)

        (q_3) edge  node {$b$} (q_4)

        (q_4) edge  [bend left] node {$a$} (q_8)

        (q_4) edge [loop right] node {$b$} ()

        (q_5) edge  node {$a$} (q_1)

        (q_5) edge  [bend left] node [below] {$b$} (q_6)

        (q_6) edge  [bend left] node {$a$} (q_5)

        (q_6) edge   node {$b$} (q_2)

        (q_7) edge   node {$a$} (q_2)

        (q_7) edge   [bend left] node {$b$} (q_8)

        (q_8) edge   [bend left] node {$a$} (q_7)

        (q_8) edge   [bend left] node {$b$} (q_4);
      \end{tikzpicture}
    \end{figure}

  \end{enumerate}

    \item Este exercício trata de linguagens sobre alfabeto de uma letra;
  para fixar as ideias, \(\Si=\{a\}\).  Dada \(L\subseteq\Sis\), denote
  \(E(L)=\conj{n\in\N}{a^n\in L}\).

  Uma \emph{progressão aritmética (PA)} de razão \(r\) é um conjunto de
  inteiros da forma \(P(h,r)=\conj{h+nr}{n\in\N}\), onde \(h,r\in\N\).
  Note que \(P(h,0)=\{h\}\).
  \begin{enumerate}
      \item Mostre que um AD sobre \Si cujos estados sejam todos acessíveis
    pode ter seus estados numerados \(0,1,\ldots,n-1\), de forma que,
    para \(i<n-1\), \(\delta(i,a)=i+1\).
      \item  Mostre que se \(E(L)\) é uma PA, então \(L\) é regular.
      \item Prove que, para \(L\subseteq\Sis\), são equivalentes:
    \begin{enumerate}
        \item \(L\) é regular.
        \item \(E(L)\) é união de um conjunto finito com uma coleção de PAs com a mesma razão.
        \item \(E(L)\) é união de uma coleção finita de PAs.
    \end{enumerate}
  \end{enumerate}

    \item Dê um exemplo de linguagem sobre alfabeto de uma letra que
  não é regular.  Use o exercício anterior e encontre uma prova
  rigorosa.


    \item \SI 1.6
    \item \SI \textbf{1.15}
    \item \SI 1.22
    \item \SI \textbf{1.37}
    \item \SI 1.38.
    \item \LP 1.7.5.
    \item \LP 1.8.3.
    \item \LP 1.8.5.
    \item\LP  2.4.3.
    \item\LP 2.4.5.
    \item\LP \textbf{2.4.6}.
    \item\LP \textbf{2.4.7}.
    \item\LP \textbf{2.4.8}.
    \item\LP 2.4.13.
    \item\LP 2.5.1.
    \item\LP  2.6.1.
    \item\LP 2.6.2.
    \item\LP \textbf{2.6.3}.
\end{enumerate}
\newpage
\noindent \textbf{B) Computabilidade}

\begin{enumerate}
    \item Mostre que uma linguagem \(L\subseteq\Sis\) é recursivamente
   enumerável sse existe uma linguagem recursiva \(H\subseteq\Sis\#\Gamma^*\)
   para algum \(\Gamma\supset\Si\) (e um símbolo especial
   \(\#\in\Gamma\backslash\Si\)) tal que
   \(L=\conj{x\in\Sis}{\text{existe}\;y\in\Gamma^*\;\text{tal que}\;x\#y\in
     H}\).  (Obs1: o \(\#\) está aí para separar componentes de um par
   ordenado; em vez de \(x\#y\), \ a definição poderia usar \((x,y)\); Obs2:
   podemos pensar no \(y\) como sendo um certificado de que \(x\in L\))

     \item Descreva em português como funcionaria uma MT para reconhecer a
   linguagem \conj{ww}{w\in\Sis}.  A MT pode ter várias fitas, ser
   não-determinística, o que você quiser. Use uma linguagem de mais ou menos
   alto nível, com operações pequenas como ``andar pela fita'', ``copiar um
   caractere'', etc.

   
     \item Mostre que a família das linguagens recursivas é fechada pelas
   operações de união, concatenação, estrela, interseção, reversão.
   
     \item É decidível, dadas duas linguagens recursivas \(L_1, L_1\), se
   \(L_1\backslash L_2\) é regular?  Recursivamente enumerável?

   
   %   \item \obr Mostre que as classes \(P\) e \(NP\) são fechadas pelas operações
   % de união, concatenação, estrela, interseção, reversão.  Use algoritmos
   % polinomiais e certificados, não se restrinja a MTs.

\end{enumerate}
\end{document}

% Local Variables: 
% mode: latex
% TeX-master: t
% End: 
