notebook.tex

% Created 2019-06-15 Sat 15:19
% Intended LaTeX compiler: pdflatex
\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage{grffile}
\usepackage{longtable}
\usepackage{wrapfig}
\usepackage{rotating}
\usepackage[normalem]{ulem}
\usepackage{amsmath}
\usepackage{textcomp}
\usepackage{amssymb}
\usepackage{capt-of}
\usepackage{hyperref}
\usepackage{minted}
\usepackage[margin=2cm]{geometry}
\usepackage{enumitem}
\DeclareMathOperator{\sign}{sign}
\setlength{\parindent}{0cm}
\date{\today}
\title{}
\hypersetup{
 pdfauthor={},
 pdftitle={},
 pdfkeywords={},
 pdfsubject={},
 pdfcreator={Emacs 26.2 (Org mode 9.2.3)}, 
 pdflang={English}}
\begin{document}


\section{Linguagens regulares}
\label{sec:org09066ab}
\subsection{Alfabetos}
\label{sec:orgcb61b58}
Um alfabeto é denotado por \(\Sigma\). Exemplos:
\[
  \Sigma = \{\, 0, 1 \,\} \qquad
  \Sigma = \{\, \text{a}, \text{b}, \text{c}, \text{d}, \text{e} \,\} \qquad
  \Sigma = \{\, \triangle, \text{O}, \square, \text{X} \,\}
\]
\subsection{Palavras}
\label{sec:org8cc1d9a}
Uma palavra (ou cadeia) é uma sequência de zero ou mais símbolos do alfabeto.
\\[5pt]
\textbf{Notação}:
\begin{align*}
  & \lambda = \varnothing \\
  & 0^4 = 0000 \\
  & \Sigma^3 = \{ 000, 001, 010, 011, 100, 101, 110, 111 \} \\
  & \Sigma^* = \bigcup_{i \in \mathbb{N}} \Sigma^i \quad \text{conjunto de todas as possíveis palavras deste alfabeto.}
\end{align*}
\textbf{Concatenação}:
\begin{gather*}
  x = 00 \qquad y = 11 \\
  xy = 0011
\end{gather*}
\textbf{Reverso}:
\[
  (xy)^{\text{R}} = 1100
\]
Observação: uma palavra \(w\) é um palíndromo se, e somente se \(w^{\text{R}} = w\).
\subsection{Linguagens}
\label{sec:org2f494dd}
Uma linguagem é um conjunto de palavras \(L \subseteq \Sigma^*\). \\[5pt]
\textbf{Operações}:
\[ L_1L_2 = \{\, xy \,\mid\, x \in L_1,\, y \in L_2 \,\} \\ \]
\begin{align*}
  & L^0 = \{\, \lambda \,\} \\
  & L^1 = L \\
  & L^2 = LL \\
  & L^* = \bigcup_{i \in \mathbb{N}} L^i \quad \text{Fecho de Kleene} \\
  & L^+ = \bigcup_{i \in \mathbb{N}^*} L^i \\
  & \varnothing^* = \{\, \lambda \,\} \\
  & \varnothing^+ = \varnothing
\end{align*}
\textbf{Teorema}: As linguagens regulares são fechadas sob as seguintes operações
\begin{itemize}[itemsep=0pt]
\item União
\item Interseção
\item Complemento
\item Concatenação
\item Fecho de Kleene
\end{itemize}
\section{Autômatos finitos}
\label{sec:orgdb0bba8}
\subsection{Determinísticos}
\label{sec:org997da3d}
Um autômato finito determinístico é definido por:
\begin{align*}
  & Q && \text{Um conjunto finito de estados.} \\
  & \Sigma && \text{Um alfabeto finito.} \\
  & \delta: Q \times \Sigma \to Q && \text{Uma função de transição.} \\
  & q_o \in Q && \text{Um estado inicial.} \\
  & F \subseteq Q && \text{Um conjunto de estados finais.}
\end{align*}
\textbf{Notação}:
\begin{align*}
  & L(M) = A \qquad \text{A linguagem reconhecida pelo autômato $M$.} \\[5pt]
  & L(M: F = \varnothing) = \varnothing \\[5pt]
  & \hat{\delta}: Q \times \Sigma^* \to Q \\
  & \hat{\delta}(e, w): \text{aplicação sucessiva de }\delta\text{ aos símbolos de }w.
\end{align*}
Ainda, nos autômatos existe um estado especial, denonimado \(\emptyset\), que aprisiona
todas as transições omitidas.
\subsubsection{Computação}
\label{sec:orga2bb7f5}
Seja \(M = (Q,\, \Sigma,\, \delta,\, q_0,\, F)\) um autômato finito determinístico, e \(w
    \in \Sigma^*\). \\
Dizemos que \(M\) aceita \(w\) se existe uma \textbf{sequência} de estados
\(r_1, \,\hdots,\, r_n \in Q\) satisfazendo:
\begin{enumerate}
\item \(r_0 = q_0\)
\item \(\forall\, i \in [0, n): \delta(r_i,\, w_{i + 1}) = r_{i + 1}\)
\item \(r_n \in F\)
\end{enumerate}
Um autômato \(M\) reconhece uma linguagem \(L\) se \(\forall\, w \in L: M \text{ aceita } w\). \\
Uma linguagem é regular se existe um autômato finito que a reconhece.
\subsubsection{Minimização de estados}
\label{sec:org2f2b012}
Dois estados \(e\) e \(e'\) são \textbf{equivalentes} se
\[
  \hat{\delta}(e, w) \in F \iff \hat{\delta}(e', w) \in F
\]
O algoritmo de minimização, então, é:
\begin{enumerate}
\item Produza uma partição \(P_0 = \{F,\, Q - F\}\) de \(Q\), separando os estados finais dos
não finais.
\item Para cada bloco de estados \(B\) na partição \(P_i\), cada símbolo \(s\) do
alfabeto \(\Sigma\), e cada par de estados (\(e\), \(e'\)) contidos no bloco B:
\begin{enumerate}
\item Sejam \(d = \delta(e, s)\) e \(d' = \delta(e' , s)\) os estados para os quais o AFD
transita quando lê o sı́mbolo \(s\) a partir dos estados \(e\) e \(e'\), respectivamente.
\item Se \(d\) e \(d'\) pertencem a blocos diferentes na partiçãoo \(P_i\), então
os estados \(e\) e \(e'\) não são equivalentes, e devem ser separados na partição
\(P_{i+1}\).
\end{enumerate}
\item Se a partição \(P_{i+1}\) for diferente da partiçãoo \(P_i\),
repita o passo 2.
\item O autômato mínimo é construído de tal forma que seus estados são os blocos da
última partição \(P\) produzida.
\end{enumerate}
\subsection{Não determinísticos}
\label{sec:org272476a}
Um autômato finito não determinístico é definido por:
\begin{align*}
  & Q && \text{Um conjunto finito de estados.} \\
  & \Sigma && \text{Um alfabeto finito.} \\
  & \delta: Q \times \Sigma \to \mathcal{P}(Q) && \text{Uma função de transição.} \\
  & I \subseteq Q && \text{Um conjunto de estados iniciais.} \\
  & F \subseteq Q && \text{Um conjunto de estados finais.}
\end{align*}
Sendo \(a \in \Sigma\) um símbolo, e \(w \in \Sigma^*\) uma palavra, define-se a função de
transição estendida:
\begin{align*}
  & \hat{\delta}: Q \times \Sigma^* \to \mathcal{P}(Q) \\
  & \hat{\delta}(\emptyset,\, w) = \{\emptyset\} \\[5pt]
  & \hat{\delta}(X,\, \lambda) = X \\[5pt]
  & \hat{\delta}(X,\, aw) = \hat{\delta}\left(\,\bigcup_{l \in X} \delta(l,\, a),\, w \right)
\end{align*}
\textbf{Teorema}: Todo AFN possui um AFD equivalente. \\
Por construção:
\begin{align*}
  & Q = \mathcal{P}(Q_{\text{afn}}) && \\
  & \Sigma = \Sigma_{\text{afn}} && \\
  & \delta(X, a) = \bigcup_{l \in X} \delta_{\text{afn}}(l,\, a) && \\
  & q_o = I_{\text{afn}} && \\
  & F = \left\{ X \subseteq Q_{\text{afn}} \,\mid\, X \cap F \neq \varnothing \right\}&&
\end{align*}
\subsubsection{Transições \(\lambda\)}
\label{sec:orgd81c3fc}
Um autômato finito não determinístico com transições \(\lambda\) introduz a
possibilidade de transições sem a consumação de símbolos.
\begin{align*}
  & Q = Q_{\text{afn}} && \\
  & \Sigma = \Sigma_{\text{afn}} && \\
  & \delta: Q \times \Sigma_{\lambda} \to \mathcal{P}(Q) && \\
  & I = I_{\text{afn}} && \\
  & F = F_{\text{afn}} &&
\end{align*}
Onde \(\Sigma_{\lambda} = \Sigma \cup \{\lambda\}\). \\[10pt]
Os estados para os quais se transita sem consumir símbolos é definido pelo fecho \(\lambda\):
\[
  \mathcal{F}_{\lambda}: \mathcal{P}(Q) \to \mathcal{P}(Q)
\]
\textbf{Teorema}: O fecho lambda de um estado é pelo menos o próprio estado.
\[
  \forall\, X \in Q: X \in \mathcal{F}_{\lambda}(\{X\})
\]
Assim, define-se a função de transição estendida:
\begin{align*}
  & \hat{\delta}: Q \times \Sigma_{\lambda}^* \to \mathcal{P}(Q) \\
  & \hat{\delta}(\varnothing, w) = \varnothing \\
  & \hat{\delta}(X, \lambda) = \mathcal{F}_{\lambda}(X) \\
  & \hat{\delta}(X, ay) = \hat{\delta} \left( \bigcup_{Y \in\, \mathcal{F}_{\lambda}(X)} \delta(Y, a),\enspace y \right)
\end{align*}
\textbf{Teorema}: Todo AFN\(\lambda\) possui um AFN equivalente. \\
Por construção:
\begin{align*}
  & Q = Q_{\text{afn}\lambda} && \\
  & \Sigma = \Sigma_{\text{afn}\lambda} && \\
  & \delta = \mathcal{F}_{\lambda} \circ \delta_{\text{afn}\lambda} && \\
  & I = \mathcal{F}_{\lambda}\left(I_{\text{afn}\lambda}\right) && \\
  & F = F_{\text{afn}\lambda} &&
\end{align*}
\subsection{Com pilha}
\label{sec:org83bf7f5}
Um autômato finito com pilha não determinístico é definido por:
\begin{align*}
  & Q && \text{Um conjunto finito de estados.} \\
  & \Sigma && \text{Um alfabeto finito.} \\
  & \Gamma && \text{Um alfabeto de pilha finito.} \\
  & \delta: Q \times \Sigma_{\lambda} \times \Gamma_{\lambda} \to \mathcal{P}\left(\Gamma^* \times Q\right) && \text{Uma função de transição.} \\
  & I \subseteq Q && \text{Um conjunto de estados iniciais.} \\
  & F \subseteq Q && \text{Um conjunto de estados finais.}
\end{align*}
Em cada transição, o elemento do topo da pilha é retirado para a função de transição,
que por sua vez devolve uma sequência de elementos a serem empilhados, além do estado
transitado. \\ \\
Um AFPN aceita uma palavra se ao consumí-la, encerra-se em um estado final \textbf{com a pilha
vazia}.
\section{Expressões regulares}
\label{sec:org717509e}
Uma expressão regular pode ser uma das seguintes formas, cada qual com a linguagem
correspondente:
\begin{align*}
  & \lambda & \{\lambda\} && \\
  & \varnothing & \varnothing && \\
  & a & \{a\} && \\
  & R_1 + R_2 & L(R_1) \cup L(R_2)  && \\
  & R_1 R_2 & L(R_1) \cdot L(R_2)  && \\
  & R^* & L(R)^* 
\end{align*}
\textbf{Operações}:
\begin{align*}
  & R^+ = RR^* && \\
  & R^0 = \lambda && \\
  & R^n = RR^{(n - 1)} &&
\end{align*}
\section{Linguagens irregulares}
\label{sec:org1e6eb30}
Nas linguagens regulares, têm se o \textbf{lema do bombardeamento}: \\
Se \(L\) é uma linguagem regular, então
\begin{align*}
  & \exists\, k \in \mathbb{N}^*: \\
  & \quad \forall\, z \in L, |z| \geq k : \\
  & \quad\quad \exists\, u, v, w: \\
  & \quad\quad\quad 1.\> z = uvw \\
  & \quad\quad\quad 2.\> |uv| \leq k \\
  & \quad\quad\quad 3.\> v \neq \lambda \\
  & \quad\quad\quad 4.\> \forall\,i \in \mathbb{N}^*: \left(uv^iw\right) \in L
\end{align*}
O lema pode ser utilizado para provar que uma dada linguagem não é regular.
\section{Linguagens livres de contexto}
\label{sec:org3457dfb}
Uma linguagem livre de contexto é uma linguagem que pode ser denotada por uma gramática
livre de contexto.
\subsection{Gramáticas livres de contexto}
\label{sec:org7af16ab}
Uma gramática livre de contexto é definida por:
\begin{align*}
  & V && \text{Um conjunto finito de variáveis.} \\
  & \Sigma && \text{Um alfabeto finito.} \\
  & R && \text{Um conjunto de regras.} \\
  & S \in V && \text{Uma variável inicial.}
\end{align*}
As regras são constituídas da seguinte forma:
\begin{enumerate}
\item O lado esquerdo de uma regra é constituído por \textbf{uma única variável}.
\item O lado direito é constituído por uma combinação de terminais e variáveis.
\end{enumerate}
Por convenção a variável inicial é a variável alvo da primeira regra. \vspace{5pt} \\
Exemplo:
\begin{align*}
  G = \big(\{A, B\}, & \, \{0, 1, 5\},\, R,\, A \big) \\
  R: \quad & A \to 0A1 \\
           & A \to B \\
           & B \to 5
\end{align*}
\textbf{Lema}: Para toda GLC, existe um AFPN que a reconhece.
\begin{align*}
  & G = (V, \Sigma, R, S) & \\
  & M = \big( \{i, f\},\> \Sigma,\> (V \cup \Sigma),\> \delta,\> \{i\},\> \{f\} \big)
\end{align*}
\begin{align*}
  \delta(i, \lambda, \lambda) & = \big\{ [f, S] \big\} \\
  \delta(f, \lambda, X) & = \big\{ [f, \beta] \>\big|\> (X \to \beta) \in R \big\} \\
  \delta(f, a, a) & = \big\{ [f, \lambda] \big\}
\end{align*}
\textbf{Lema}: Para todo AFPN, existe uma GLC equivalente. \newpage
Nas linguagens livres de contexto, têm se o \textbf{lema do bombardeamento}: \\
Se \(L\) é uma linguagem livre de contexto, então
\begin{align*}
  & \exists\, k \in \mathbb{N}^*: \\
  & \quad \forall\, w \in L, |w| \geq k : \\
  & \quad\quad \exists\, u, v, x, y, z: \\
  & \quad\quad\quad 1.\> w = uvxyz \\
  & \quad\quad\quad 2.\> |vxy| \leq k \\
  & \quad\quad\quad 3.\> vy \neq \lambda \\
  & \quad\quad\quad 4.\> \forall\,i \in \mathbb{N}^*: \left(uv^ixy^iz\right) \in L
\end{align*}
O lema pode ser utilizado para provar que uma dada linguagem não é livre de contexto.
\subsection{Forma normal de Chomsky}
\label{sec:org1d476f0}
Uma gramática livre de contexto está na forma normal de Chomsky se todas as suas regras
de produção estão em uma das seguintes formas:
\begin{align*}
  & A \to BC && \text{Combinação de duas variáveis.} \\
  & A \to \alpha && \text{Um único terminal.} \\
  & S \to \lambda && \text{Variável vazia.}
\end{align*}
Onde apenas \(A\) e \(S\) podem ser a variável inicial. \\ \\
\textbf{Teorema}: toda gramática livre de contexto pode ser transformada para a forma normal
de Chomsky.
\subsection{Propriedade de fechamento}
\label{sec:org89ba51a}
A classe das linguagens livre de contexto são fechadas sob as seguintes operações
\begin{itemize}[itemsep=0pt]
\item União
\item Concatenação
\item Fecho de Kleene
\end{itemize}
\pagebreak
\section{Máquinas de Turing}
\label{sec:org5f071e5}
Uma máquina de Turing é definida por:
\begin{align*}
  & Q && \text{Um conjunto finito de estados.} \\
  & \Sigma && \text{Um alfabeto de linguagem finito.} \\
  & \Gamma \supset \Sigma && \text{Um alfabeto de fita finito, no qual $\Sigma$ está contido.} \\
  & \langle \enspace \in \Gamma && \text{Um demarcador do começo da fita.} \\
  & \phi \in \Gamma && \text{Um símbolo nulo.} \\
  & \delta: Q \times \Gamma \to Q \times \Gamma \times \{E, D\} && \text{Uma função de transição.} \\
  & i \in Q && \text{Um estado inicial.} \\
  & F \subseteq Q && \text{Um conjunto de estados finais.}
\end{align*}
Esta máquina possui uma fita, que inicialmente é
\[
  \left[\langle\,\Sigma^*\,\phi^\infty\right]
\]
A função de transição percorre a fita, consumindo símbolos e produzindo um estado alvo,
o símbolo a substituir o símbolo atual, e a direção do próximo
caminhamento. \\ \\
O demarcador limita o caminhamento à esquerda, ao contrário do caminhamento à direita
que é ilimitado:
\[
  \forall\> \delta, e \in Q: \>\delta\big(e, \langle\,\big) = \left[\,e',\, \langle\,,\, D\,\right]
\]
A máquina aceita uma palavra caso a transição estendida sobre esta palavra \textbf{encerra} em um
estado final. Ao contrário dos autômatos, a máquina não transita implicitamente para um
estado de erro quando a transição é indefinida. Neste caso, a máquina encerra a
execução no estado corrente.
\section{Linguagens recursivas e recursivamente enumeráveis}
\label{sec:orge234436}
Linguagens recursivamente enumeráveis são as linguagens reconhecidas por uma máquina de
turing. \\
Linguagens recursivas são as linguagens reconhecidas por uma máquina de turing que
\textbf{sempre encerra}. \\ \\
Portanto, as linguagens recursivas são um subconjunto das linguagens recursivamente
enumeráveis.
\subsection{Gramáticas Irrestritas}
\label{sec:org107e8c3}
Uma gramática irrestrita é dada por
\begin{align*}
  & V && \text{Um conjunto finito de variáveis.} \\
  & \Sigma && \text{Um alfabeto finito.} \\
  & R = \left\{ \alpha \to \beta \enspace\big|\enspace \alpha \in \left(V \cup \Sigma\right)^+,\> \beta \in \left(V \cup \Sigma\right)^* \right\} && \text{Um conjunto de regras.} \\
  & S \in V && \text{Uma variável inicial.}
\end{align*}
As regras são constituídas da seguinte forma:
As linguagens geradas por gramáticas irrestritas são linguages recursivamente
enumeráveis.
\section{Linguagens Sensíveis ao Contexto}
\label{sec:org51ffc69}
\subsection{Gramáticas Sensíveis ao Contexto}
\label{sec:org7f59faf}
Uma gramática sensível ao contexto é dada por
\begin{align*}
  & V && \text{Um conjunto finito de variáveis.} \\
  & \Sigma && \text{Um alfabeto finito.} \\
  & R = \left\{ \alpha \to \beta \enspace\big|\enspace \alpha, \beta \in \left(V \cup \Sigma\right)^+,\> |\alpha| \leq |\beta| \right\} && \text{Um conjunto de regras.} \\
  & S \in V && \text{Uma variável inicial.}
\end{align*}
As gramáticas sensíveis ao contexto são \textbf{mais restritas} que as gramáticas irrestritas.
\section{Autômato linearmente limitado}
\label{sec:orgcee5c6f}
Um autômato linearmente limitado é uma maquina de turing não determinística com uma fita
limitada:
\begin{align*}
  & Q && \text{Um conjunto finito de estados.} \\
  & \Sigma && \text{Um alfabeto de linguagem finito.} \\
  & \Gamma \supset \Sigma && \text{Um alfabeto de fita finito, no qual $\Sigma$ está contido.} \\
  & \langle \enspace \in \Gamma && \text{Um demarcador do começo da fita.} \\
  & \rangle \enspace \in \Gamma && \text{Um demarcador do fim da fita.} \\
  & \phi \in \Gamma && \text{Um símbolo nulo.} \\
  & \delta: Q \times \Gamma \to \mathcal{P}\big(Q \times \Gamma \times \{E, D\}\big) && \text{Uma função de transição não determinística.} \\
  & i \in Q && \text{Um estado inicial.} \\
  & F \subseteq Q && \text{Um conjunto de estados finais.}
\end{align*}
Esta máquina possui uma fita, que inicialmente é
\[
  \left[\langle\,\Sigma^* \rangle\right]
\]
\section{Hierarquia de Chomsky}
\label{sec:orga8ea8c4}
Chomsky definiu a seguinte hierarquia das linguagens:
\begin{table}[H]
  \centering
  \left\downarrow
  \begin{tabular}{l}
    $\mathcal{P}(\Sigma^*) \qquad$ Qualquer conjunto de palavras \\
    Linguagens Recursivamente Enumeráveis \\
    Linguagens Recursivas \\
    Linguagens Sensíveis ao Contexto \\
    Linguagens Livres de Contexto \\
    Linguagens Regulares
  \end{tabular}
  \right.
\end{table}
\textbf{Tese de Church-Turing}: Se uma função é computável, ela pode ser computada pela máquina
de Turing.
\end{document}