ap3.png

Automatos_Lista_6.pdf

Automatos_Lista_6.tex

\documentclass{article}

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

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

\begin{document}

\maketitle

\section{Problema 1}
	\subsection{Declaração}
		Dê gramáticas livres-do-contexto que gerem as seguintes linguagens. Em todos os itens o alfabeto $\Sigma$ é $\{ 0 , 1 \}$.
		% 2.4e
		\begin{itemize}
			\item $\{ w \mid w = w^R , $ ou seja, $w$ é uma palíndrome $\}$
		\end{itemize}
		
	\subsection{Solução}	
		A gramática livre-do-contexto que gera a linguagem dado é:
			\[ S \rightarrow 0 \mid 1 \mid 0T0 \mid 1T1 \]
			\[ T \rightarrow 0 \mid 1 \mid \varepsilon \]

\section{Problema 2}
	\subsection{Declaração}
		% 2.6d
		Dê gramáticas livres-do-contexto gerando as seguintes linguages.
		\begin{itemize}
			\item $\{ x_1\#x_2\#{\ldots}\#x_k \mid k \geq 1, $ cada $x_i \in \{ a , b \}^* , $ e para algum $i$ e $j$ , $x_i = x_j^R \}$
		\end{itemize}

	\subsection{Solução}
		A gramática livre-do-contexto que gera a linguagem dado é:
			\[ S \rightarrow P\#R \]
			\[ R \rightarrow X \mid X\#R \]
			\[ P \rightarrow a \mid b \mid aQa \mid bQb \]
			\[ Q \rightarrow a \mid b \mid \varepsilon \]
			\[ X \rightarrow aY \mid bY \]
			\[ Y \rightarrow aY \mid bY \mid \varepsilon \]
		Dado que $P$ gera uma palíndrome se cumple a condição $x_i = x_j^R$ para algum $i$ e $j$ porque para $i = j$ é verdadeiro.

\section{Problema 3}
	\subsection{Declaração}
		% 2.12
		Converta a GLC $G$ dada no exercício 2.3 para um AP equivalente, usando o procedimento dado no Teorema 2.20.
			\[ R \rightarrow XRX \mid S \]
			\[ S \rightarrow aTb \mid bTa \]
			\[ T \rightarrow XTX \mid X \mid \varepsilon \]
			\[ X \rightarrow a \mid b \]

	\subsection{Solução}
		A figura~\ref{fig:glc} mostra o AP equivalente para a GLC $G$.
		\begin{figure}[ht]
			\centering
			\includegraphics[width=\textwidth,height=8.44cm]{ap3}
			\caption{AP equivalente para $G$}
			\label{fig:glc}
		\end{figure}
	
\section{Problema 4}
	\subsection{Declaração}
		% 2.20
		Seja $A / B = \{ w \mid wx \in A $ para algum $x \in B \}$. Mostre que, se $A$ é livre do contexto e $B$ é regular, então $A / B$ é livre do contexto.

	\subsection{Solução}

\section{Problema 5}
	\subsection{Declaração}
		% 2.25
		Para qualquer linguagem $A$, seja ${SUFFIX}( A ) = \{ v \mid uv \in A $ para alguma cadeia $u \}$. Mostre que a classe de linguagens livres-do-contexto é fechada sob a operação ${SUFFIX}$.

	\subsection{Solução}

\section{Problema 6}
	\subsection{Declaração}
		% 2.30d
		Use o lema do bombeamento para mostrar que as seguintes linguagens não são livres do contexto.
		\begin{itemize}
			\item $L = \{ t_1\#t_2\#{\ldots}\#t_k \mid k \geq 2 , $ cada $t_i \in \{ a , b \}^* , $ e $t_i = t_j$ para algum $i \neq j \}$
		\end{itemize}

	\subsection{Solução}
		Temos uma cadeia $w = a^nb\#a^nb \in L$ na linguagem dado. Pelo lema do bombeamento existe um $p$ tal que $w = a^pb\#a^pb$ aceita uma fatoração $w = uvxyz$ tal que:
		\begin{itemize}
			\item $uv^ixy^iz \in L$, para $i \geq 0$
			\item $|vy| > 0$
			\item $|vxy| \geq p$
		\end{itemize}
		Para $w$ temos os seguintes possíveis casos:
		\begin{itemize}
			\item Se $vxy$ só tem $a$s, então ao bombear $w$ terá mais $a$s de um lado e não cumplirá com a condição da linguagem "Para algum $i \neq j, t_i = t_j$" porque ambas cadeias aos lados do símbolo $\#$ são diferentes.
			\item Se $vxy$ tem $a$s seguida de uma $b$, então ao bombear para qualquer valor de $v$ e $y$ terá mais $a$s e $b$s de um lado e não cumplirá com a condição já mencionada no caso anterior.
			\item Se $vxy$ começa com $b$, então para qualquer valor de $v$ e $y$, sempre mudará o valor de um lado e não cumplirá com a condição da linguagem.
			\item O mesmo ocurre para os casos em que $vxy$ está ao lado direito do simbolo $\#$
		\end{itemize}
		Portanto, a cadeia $w$ não admite uma fatoração que cumple com o lema e a linguagem $L$ não é livre do contexto.

\section{Problema 7}
	\subsection{Declaração}
		% 2.31
		Seja $B$ a linguagem de todas as palíndromes sobre $\{ 0 , 1 \}$ contendo o mesmo número de $0$s e $1$s. Mostre que $B$ não é livre do contexto.

	\subsection{Solução}
		Para qualquer cadeia $w$, definimos $O( w ) = $ número de $1$s em $w$, e $Z( w ) = $ número de $0$s em $w$. Então:
			\[ B = \{ w \mid w \in \{ 0 , 1 \}^* , w = w^R , O( w ) = Z( w ) \} \]
		Temos uma cadeia $w = 0^n1^{2n}0^n \in B$ e pelo lema do bombeamento existe um $p$ tal que $w = 0^p1^{2p}0^p$ admite uma fatoração que cumple:
		\begin{itemize}
			\item $uv^ixy^iz \in L$, para $i \geq 0$
			\item $|vy| > 0$
			\item $|vxy| \geq p$
		\end{itemize}
		Para $w$ temos os seguintes possíveis casos:
		\begin{itemize}
			\item Se $vxy$ só tem $0$s, para qualquer valor de $v$ e $y$, ao bombear terá mais $0$s de um lado e não será palíndrome.
			\item Se $vxyy$ contem $0$s e $1$s, para qualquer valor de $v$ e $y$, ao bombear pode ocurrir dois casos, se $v$ e $y$ tem igual comprimento, então o número de $1$s e $0$s vai ser igual, mas não será um palíndrome. O segundo caso se $v$ e $y$ com diferente comprimento, então o número de $0$s e $1$s vai ser diferente e não estará em $B$.
			\item Se $vxy$ só tem $1$s, então para qualquer valor de $v$ e $y$, ao bombear ocurrirá que $O( w ) > Z( w )$.
		\end{itemize}
		Portanto, para todas as fatorações de $w$, não cumple com as tres condições do lema do bombeamento e então $B$ não é livre do contexto.

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

\end{document}