Automatos_Lista_5.pdf

Automatos_Lista_5.tex

\documentclass{article}

\usepackage{lmodern}
\usepackage[]{algorithm2e}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[portuguese]{babel}
\usepackage{mathtools}
\usepackage{enumitem}

\usepackage{amsthm}
\newtheorem*{remark}{Teorema}

\title{Lista 5 de Linguagens, Autômatos e Computabilidade}
\author{9410313 - Walter Perez Urcia}

\begin{document}

\maketitle

\section{Problema 1}
	\subsection{Declaração}
		Na seção, PROJETANDO GRAMÁTICAS LIVRES-DO-CONTEXTO, considere o exemplo em que uma gramática livre de contexto é construída a partir de um autômato finito. Demonstre que a linguagem associada à gramática ali construída é a mesma reconhecida pelo autômato original.
		
	\subsection{Solução}	
		

\section{Problema 2}
	\subsection{Declaração}
		Demonstre que o autômato a pilha construído no lema 2.21 em~\cite{Sipser04} reconhece a mesma linguagem que é associada à gramática a partir da qual o autômato a pilha foi construído.

	\subsection{Solução}
		Seja $L( G )$ a linguagem livre de contexto em questão e seja $G = (V, \Sigma, R, S)$ uma gramática que gera $L( G )$. Seja $A$ o autômato construído na prova. Vamos lembrar que esse autômato tem basicamente três "macroestados": o estado de início, o estado de loop e um estado final. Queremos mostrar que $L( A ) = L( G )$. Sendo assim, considerem a seguinte afirmação:

"Seja $w$ uma palavra composta apenas por terminais, ou seja, w pertence a $\Sigma^*$. Seja $X$ a palavra vazia ou uma concatenação qualquer de variáveis e terminais de $G$ começando com uma variável. Então, partindo da variável de início $S$ de $G$, conseguimos gerar $wX$ por uma sucessão de regras de $G$ se, e somente se, existe uma computação do autômato $A$ que vai do estado inicial e passa pelo estado de loop após ter processado um trecho $w$ da palavra de entrada e precisamente com $X\$$ na pilha."

Aqui vão algumas considerações:

1) Reparem que essa afirmação é do tipo "se, e somente se"; logo, para prová-la, vocês precisam provar, como de costume, a ida e a volta;

2) Eu afirmo que, para provar a corretude do autômato A, é suficiente provar a afirmação acima (pensem no porquê isso é verdade e justifiquem antes de começar a provar a afirmação);

3) Como falei no item 1, essa afirmação é do tipo "se, e somente se". Então, para provar a ida, minha sugestão é: façam indução no comprimento de uma derivação mais à esquerda de $w$ por $S$. Para provar a volta, minha sugestão é: façam indução no número de vezes que a computação em questão passa por "supertransições" (uma supertransição é qualquer uma daquelas transições que saem do estado de loop e entram no estado de loop).

\bibliographystyle{plain}   
\bibliography{bibliography.bib}

\end{document}

bibliography.bib

@book{Sipser04,
	author = {{Michael Sipser}} ,
	title = {{Introduction to the Theory of Computation, 2nd Edition}} ,
	year = {2004}
}