Automatos_Lista_2.pdf

Automatos_Lista_2.tex

\documentclass{article}

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

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

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

\begin{document}

\maketitle

\section{Problema 1}
	\subsection{Declaração}
		Demonstre que a construção presente na prova do teorema 1.25 (A classe de linguagens regulares é fechada sob a operação de união) rec,onhece a união das linguagens como prometido.
		\begin{remark}
			A classe de linguagens regulares é fechada sob a operação de união. Em outras palavras, se $A_1$ e $A_2$ são linguagens regulares, o mesmo acontece com $A_1 \cup A_2$.
		\end{remark}
		A construção do teorema é da seguinte forma: \\
		\begin{center}
			$M_1$ reconhece $A_1$, onde $M_1 = ( Q_1 , \sigma , \delta_1 , q_1 , F_1 )$ \\
			$M_2$ reconhece $A_2$, onde $M_2 = ( Q_2 , \sigma , \delta_2 , q_2 , F_2 )$ \\
		\end{center}
		Então: \\
		\begin{center}
			$M$ reconhece $A = A_1 \cup A_2$, onde $M = ( Q , \sigma , \delta , e_0 , F )$\\
		\end{center}
		Onde: \\
		\begin{enumerate}
			\item $Q = Q_1 \times Q_2$
			\item $\sigma$ é o mesmo para os dos
			\item Para cada $( r_1 , r_2 ) \in Q$ ( com $r_1 \in Q_1$ e $r_2 \in Q_2$ ), $\delta( ( r_1 , r_2 ) , a ) = ( \delta_1( r_1 , a ) , \delta_2( r_2 , a ) )$
			\item $e_0 = ( q_1 , q_2 )$
			\item $F = (F_1 \times Q_2) \cup (Q_1 \times F_2)$
		\end{enumerate}
	\subsection{Solução}
		\textbf{Prova por contradição:}\\
		Se temos uma palavra $w = a_1a_2a_3{\ldots}a_m \in A_2 \cup A_2$ que é aceitada por $M$, então não pode existir um estado $E \not \in Q$ na sequencia de estados.\\
		Para $w$ temos uma sequencia de estados $e_0e_1e_2{\ldots}e_m$ no autômato $M$. Se denotamos $e_{k_1}$ ($\in Q_1$) para a primeira componente de $e_k$ e como $e_{k_2}$ ($\in Q_2$) para a segunda componente, então para a sequencia de estados temos:
		\begin{itemize}
			\item $e_0 = ( q_1 , q_2 )$
			\item $e_{k+1} = ( \delta_1( e_{k_1} , a_{k+1}  ) , \delta_2( e_{k_2} , a_{k+1} ) $)
		\end{itemize}
		Tendo em conta que $r_1 = e_{k_1} \in Q_1$ e $r_2 = e_{k_2} \in Q_2$, e que os valores retornados por $\delta_1 \in Q_1$ e $\delta_2 \in Q_2$, então $e_{k+1} \in Q$. Além, para que uma cadeia seja aceitada pelo autômato $e_m \in F$, mas $F \subset Q$ e portanto a construção sempre vai reconhecer $A_1 \cup A_2$ porque não existe algum elemento $E \not \in Q$.
		
\section{Problema 2}
	\subsection{Declaração}
		Demonstre que toda linguagem finita admite um autômato finito que a reconheça. Sugestão: Faça uma indução finita em n, o número de palavras presentes na linguagem.
	\subsection{Solução}
		\textbf{Prova por indução:} Em $n = $número de palavras na linguagem.\\
		Seja $M_k$ um autômato que reconhece um linguagem finito com $k$ palavras.\\
		\\
		\textbf{Base}: $n = 1$
		Se temos uma palavra $w = x_0x_1x_2{\ldots}x_{|w|-1}$ ($|w| = $longitud de $w$) podemos ter um autômato $M_1 = ( Q_1 , \Sigma_1 , \delta_1 , q_0 , F_1 )$ que a reconheça então existe uma sequencia de estados $S_1 = q_0q_1q_2{\ldots}q_{|w|}$. Onde:
		\begin{itemize}
			\item $Q_1 = \{ q_i \mid q_i \in S_1 \}$
			\item $\Sigma_1 = \{ x_i \mid x_i \in w \}$
			\item A função de transição vai ser: $\delta_1( q_i , x_i ) = q_{i+1}$
			\item O estado inicial: $q_0$
			\item $F_1 = q_{|w}$
		\end{itemize}
		
		\textbf{Paso de indução}: Para $n > 1$
		Temos um autômato $M_n = ( Q_n , \Sigma_n , \delta_n , q_0 , F_n )$ que va a reconhecer a linguagem finito com $n$ palavras. Se temos uma palavra $z = y_0y_1{\ldots}y_{|z|-1}$ aceitada com uma sequencia de estados $S_{n+1} = r_0r_1r_2{\ldots}r_{|z|}$ então o autômato $M_{n+1} = ( Q_{n+1} , \Sigma_{n+1} , \delta_{n+1} , q_0 , F_{n+1} )$ vai ser da seguinte forma:
		\begin{itemize}
			\item $Q_{n+1} = Q_n \cup \{ r_i \mid r_i \in S_{n+1} \}$
			\item $\Sigma_{n+1} = \Sigma_n \cup \{ y_i \mid y_i \in z \}$
			\item Para a função de transição $\delta_{n+1}$ vai ter todas as transições em $\delta_n$ mais todas as transições da forma $\delta( r_i , y_i ) = r_{i+1}$ para $0 \leq i < |z| $
			\item O estado inicial vai ser o mesmo sempre porque só vai ser necessário adicionar uma transição em caso $q_1 \neq r_1$
			\item $F_{n+1} = F_n \cup r_{|z|}$
		\end{itemize}
		Por tanto, o autômato $M_{n+1}$ aceita um linguagem com $n+1$ palavras.

\end{document}