Skip to content

Instantly share code, notes, and snippets.

@NonWhite

NonWhite/Automatos_Lista_6.pdf

Last active August 29, 2015 14:22
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save NonWhite/beaccf4c8d88cf648bc6 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save NonWhite/beaccf4c8d88cf648bc6 to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
Automatos_Lista_6.pdf
View raw
Raw
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}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment