Last active
August 29, 2015 14:20
-
-
Save NonWhite/6ad63062a78ab267e90a to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| \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} |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| @book{Sipser04, | |
| author = {{Michael Sipser}} , | |
| title = {{Introduction to the Theory of Computation, 2nd Edition}} , | |
| year = {2004} | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment