Automatos_Lista_4.pdf

Automatos_Lista_4.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 4 de Linguagens, Autômatos e Computabilidade}
\author{9410313 - Walter Perez Urcia}

\begin{document}

\maketitle

\section{Problema 1}
	\subsection{Declaração}
		Prove that the following languages are not regular. You may use the pumping lemma and the closure of the class of regular languages under union, intersection, and complement.
		\begin{enumerate}[ label = \textbf{\alph*.} ]
			\item $A = \{ 0^n1^m0^n \mid m,n \geq 0 \}$
			\item $B = \{ 0^m1^n \mid m \neq n \}$
			\item $C = \{ w \mid w \in \{ 0 , 1 \}^* $ is not palindrome $\}$
			\item $D = \{ wtw \mid w , t \in \{ 0 , 1 \}^+ \}$
		\end{enumerate}

	\subsection{Solução}		
		\subsubsection{Parte a)}
		\label{subsub:1a}
			\textbf{Prova por contradição:} Assumindo que $A$ é regular\\
			Como é possível que $n = m$, então podemos ter uma cadeia $s = 0^n1^n0^n$.
			Seja $p$ o tamanho dado por o pumping lemma, então temos $s = 0^p1^p0^p$ que pode ser dividido em tres partes da forma $s = xyz$ e que para $i \geq 0$, $s = xy^iz \in A$. Se temos $x = 0^{p-1}$, $y = 0$ e $z = 1^p0^p$ e tentamos fazer $s = xyyz$ este não vai estar em $A$ porque terá mais 0s de um lado. Portanto, $A$ não é regular.
		
		\subsubsection{Parte b)}
			Para provar que $B$ não é regular usamos o closure de linguagens regulares.\\
			Se temos $\overline{B} \cap 0^*1^*$ esto vai ser igual a $X = \{ 0^k1^k \mid k \geq 0 \}$ porque em $B$ os valores de $m$ e $n$ sempre são diferentes, mas em seu complemento sempre são iguais, ao intersectar esto com $0^*1^*$ teremos o novo linguagem mostrado anteriormente. Por o closure temos que se $B$ é regular, seu complemento também e a interseção também, mas a interseção não é regular e portanto, $B$ não é regular.\\
			\textbf{Prova por contradição:} Assumindo que $X$ é regular\\
			Por o pumping lemma, temos uma cadeia $s = 0^p1^p$ sendo $p$ o tamanho dado por o pumping lemma, então podemos dividir $s = xyz \in X$ da forma $x = 0^{p-1}$, $y = 0$ e $z = 1^p$. Por o lemma, $s = xyyz$ também ter que estar em $X$, mas não é verdade porque terá mais 0s que 1s. Portanto, $X$ não é regular.
		
		\subsubsection{Parte c)}
			\textbf{Prova por contradição:} Assumindo que $C$ é regular\\
			Se $\overline{C} = \{ w \mid w \in \{ 0 , 1 \}^* $ is palindrome $\}$ é regular então $C$ também é regular, mas por o pumping lemma temos $s = 0^p1^p0^p \in \overline{C}$. Por o mostrado em \ref{subsub:1a} podemos saber que $\overline{C}$ não é regular e portanto, $C$ não é regular.
		
		\subsubsection{Parte d)}
			Definimos $w = 0^n$ e $t = 1^m$ (com $m,n > 0$), então temos $s = wtw = 0^n1^m0^n$, por a prova em \ref{subsub:1a}, $D$ não é regular.

\section{Problema 2}
	\subsection{Declaração}
		Let $\Sigma = \{ 1 , \# \}$ and let\\
		$Y = \{ w \mid w = x_1\#x_2\#{\ldots}\#x_k $ for $ k \geq 0$, each $x_i \in 1^*$, and $x_i \neq x_j $ for $i \neq j \}$
		\\
		Prove that $Y$ is not regular.

	\subsection{Solução}
		\textbf{Prova por contradição:} Assumindo que $Y$ é regular\\
		Como para todo $x_i \neq x_j, i \neq j$, ou seja todos os $x_i$ são diferentes, podemos fazer $x_i = 1^i$.\\
		Por o pumping lemma temos um valor $p$ tal que $w = 1^1\#1^2\#{\ldots}\#1^p = xyz \in Y$ com $x = \varepsilon$, $y = 1$ e $z = \#1^2\#{\ldots}\#1^p$. Se fazemos $w = xyyz$ este não vai estar em $Y$ porque será da forma $w = 1^2\#1^2\#\ldots$ e não cumple que $x_i \neq x_j$. Portanto, $Y$ não é regular.

\section{Problema 3}
	\subsection{Declaração}
		Let $\Sigma = \{ 0 , 1 \}$ and let \\
		$D = \{ w | w $ contains an equal number of ocurrences of the substrings $01$ and $10 \}$.
		\\
		Thus $101 \in D$ because $101$ contains a single $01$ and a single $10$, but $1010 \not \in D$ because $1010$ contains two $10$s and one $01$. Show that $D$ is a regular language.

	\subsection{Solução}
		Para provar que $D$ é regular temos que encontrar uma autômato finito que o reconheça ou uma expressão regular que a represente.
		\begin{itemize}
			\item As cadeias $1^*$ e $0^* \in D$
			\item Por os exemplos sabemos que as cadeias $101$ e $010 \in D$, mas $1001$ e $00010$ também estão em $D$
			\item Para cumplir com o anterior temos $1^+0^*1^+$ e $0^+1^*0^+ \in D$ porque sempre temos que ter um $10$ por cada $01$
			\item Mas anteriores cadeias não permitem cadeias como $1011001$ que também estão em $D$, esto pode ser conseguido fazendo $(1^+0^*1^+)^*$ e $(0^+1^*0^+)^* \in D$
		\end{itemize}
		Então podemos dizer que a expressão regular $E = 1^* \cup 0^* \cup (1^+0^*1^+)^* \cup (0^+1^*0^+)^*$ representa o linguagem $D$ e portanto $D$ é regular.
		
\section{Problema 4}
	\subsection{Declaração}
		\begin{enumerate}[ label = \textbf{\alph*.} ]
			\item Let $B = \{ 1^ky \mid y \in \{ 0 , 1 \}^* $ and $y$ contains at least $k$ 1s, for $k \geq 1 \}$.
			\item Let $B = \{ 1^ky \mid y \in \{ 0 , 1 \}^* $ and $y$ contains at most $k$ 1s, for $k \geq 1 \}$.
		\end{enumerate}
		
	\subsection{Solução}
		\subsubsection{Parte a)}
			Como a restrição só é para $y$, então o linguagem $B$ aceita todas as cadeias que começam com 1 e tem por o menos um 1 logo ($k \geq 1$). Para provar que $B$ é regular, devemos encontrar uma expressão regular que o represente. A expressão regular que representa $B$ será $10^*1(0|1)^*$ porque sempre começa com 1 e tem por o menos um 1 depois.
		
		\subsubsection{Parte b)}
			
	
\section{Problema 5}
\label{sec:prob5}
	\subsection{Declaração}
		Let $x$ and $y$ be strings and let $L$ be any language. We say that $x$ and $y$ are \textbf{distinguishable by $L$} if some string $z$ exists whereby exactly one of the strings $xz$ and $yz$ is a member of $L$; otherwise, for every string $z$, we have $xz \in L$ whenever $yz \in L$ and we say that $x$ and $y$ are \textbf{indistinguishable by $L$}. If $x$ and $y$ are indistinguishable by $L$ we write $x \equiv_L y$. Show that $\equiv_L$ is an equivalence relation.

	\subsection{Solução}
		Para provar que $\equiv_L$ é uma relação equivalente temos que provar que é simétrica, reflexiva e transitiva.
		\subsubsection{Simétrica}
			Se temos qualquer cadeias $x, y$. Para qualquer cadeia $w$ que satisfaz $xw \in L$ e $yw \in L$ podemos dizer que $x \equiv_L y$. Além, é trivial provar que $y \equiv_L x$ também é satisfeito. Por tanto, $\equiv_L$ é simétrica.
		
		\subsubsection{Reflexiva}
			Se temos qualquer cadeias $x$ e $y$, só podemos ter $xy \in L$ iff $xy \in L$, então $x \equiv_L x$ e portanto a relação é reflexiva.
		\subsubsection{Transitiva}
			Para qualquer cadeias $x,y,z$ temos que provar que se $x \equiv_L y$ e $y \equiv_L z$ então $x \equiv_L z$. Se $x \equiv_L y$ então existe uma cadeia $w$ tal que $xw \in L$ e $yw \in L$. Mas $y \equiv_L z$ e portanto, $zw \in L$. Com esto podemos dize que si $xw \in L$ e $zw \in L$, então $x \equiv_L z$ e a relação é transitiva.
		\\\\
		Portanto, $\equiv_L$ é uma relação equivalente.

\section{Problema 6}
	\subsection{Declaração}
		\textbf{Myhill-Nerode theorem.} Refer to Problem~\ref{sec:prob5}. Let $L$ be a language and let $X$ be a set of strings. Say that $X$ is \textbf{pairwise distinguishable by $L$} if every two distinct strings in $X$ are distinguishable by $L$. Define the \textbf{index of $L$} to be the maximum number of elements in any set that is pairwise distinguishable by $L$. The index of $L$ may be finite or infinite.
		
		\begin{enumerate}[ label = \textbf{\alph*.} ]
			\item Show that, if $L$ is recognized by a DFA with $k$ states, $L$ has index at most $k$.
			\item Show that, if the index of $L$ is a finite number $k$, it is recognized by a DFA with $k$ states.
			\item Conclude that $L$ is regular iff it has finite index. Moreover, its index is the size of the smallest DFA recognizing it.
		\end{enumerate}

	\subsection{Solução}
		Basada na solução em~\cite{Sipser04}.
		\subsubsection{Parte a)}
		\label{subsub:prob6a}
			\textbf{Prova por contradição:} Assumindo que $L$ tem um indice maior a $k$
			Para que $L$ tenha um indice maior a $k$, devemos ter um conjunto $X$ com mais de $k$ elementos e o DFA só tem $k$ estados, então por o pidgeonhole principle temos que para duas cadeias $x, y \in X$, terminaram no mesmo estado, ou seja $transição( x ) = transição( y )$ (sendo transição o estado final logo de processar a cadeia dada). Além, por definição de distinguishable temos que isso também será satisfeito só por um $xz$ e $yz$ para qualquer cadeia $z$, mas esto não é possível porque terão que satisfazer para ambas o nenhuma contradizendo a afirmação inicial.
		
		\subsubsection{Parte b)}
		\label{subsub:prob6b}
		
		\subsubsection{Parte c)}
			Usando as provas em~\ref{subsub:prob6a} e~\ref{subsub:prob6b} temos que se $L$ é regular e o DFA que reconhece tem $k$ estados. Então de~\ref{subsub:prob6a} temos que seu indice é como máximo $k$. Além, de~\ref{subsub:prob6b}, se $L$ tem indice $k$, então é reconhecido por um DFA com $k$ estados e então $L$ é regular. Por último para provar que o indice de $L$ é o tamanho do mais pequeno DFA que o reconhece podemos usar as provas anteriores. Por~\ref{subsub:prob6b} temos que um DFA com $k$ estados reconhece $L$ e por~\ref{subsub:prob6a} sabemos que não pode ser mais pequeno.

\section{Problema 7}
	\subsection{Declaração}
		Consider the language $F = \{ a^ib^jc^k \mid i , j , k \geq 0 $ and if $i = 1$ then $j = k \}$.
		
		\begin{enumerate}[ label = \textbf{\alph*.} , ref = (\alph*)]
			\item \label{en:prob7a} Show that $F$ is not regular.
			\item \label{en:prob7b} Show that $F$ acts like a regular language in the pumping lemma. In other words, give a pumping length $p$ and demonstrate that $F$ satisfies the three conditions of the pumping lemma for this value of $p$.
			\item Explain why parts~\ref{en:prob7a} and~\ref{en:prob7b} do not contradict the pumping lemma. 
		\end{enumerate}

	\subsection{Solução}
		\subsubsection{Parte a)}
			\textbf{Prova por contradicão:} Assumendo que $F$ é regular\\
			Se $F$ é regular, então existe um valor $p$ e uma cadeia $s \in F$ que pode ser dividida em tres partes da $s = xyz$ e além, $s = xyyz \in F$.\\
			Se $i = 1$, então $j = k$ e temos $s = ab^pc^p = xyz$. Fazemos $x = a$, $y = b$ e $z = b^{p-1}c^p$. Mas $s = xyyz \not \in F$ porque vai ter mais $b$s que $c$s. Por tanto $F$ não é regular.
			
		\subsubsection{Parte b)}
			Se $i > 1, j = 1, i < k$ temos por o pumping lemma a cadeia $s = a^{p-1}bc^p = xyz$ com $x = a^{p-1}$, $y = b$ e $z = c^p$ que cumple con as tres condicões:
			\begin{itemize}
				\item $xy^iz \in F$ para $i \geq 0$
				\item $|y| > 0$
				\item $|xy| \leq p$
			\end{itemize}
		
		\subsubsection{Parte c)}
			Não se contradiz porque para a demonstração de que um linguagem não é regular usando o pumping lemma ter que usar a cadeia correta e não sempre é fácil encontrá-la, como no exemplo 1.75 em~\cite{Sipser04}.

\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}
}