Rogério Reis


Err and err and err again, but less and less and less.


Exercícios

Folha de Trabalho 8
  1. Qual a complexidade das seguintes linguagens?

    1. Member\(={\left\{ {\left\langle a,l\right\rangle}\mid l\text{ lista, } a\in l \right\}}\)

    2. Knapsack\(={\left\{ {\left\langle K, n\right\rangle}\mid K\in 2^{{\mathbb{N}}}, K\text{ finito,} \exists S\subseteq K\;n=\sum_{k\in S}k \right\}}\)

    3. Connected\(={\left\{ {\left\langle G\right\rangle}\mid G\text{ é um grafo conexo} \right\}}\)

    4. RelPrime=\({\left\{ {\left\langle n,m\right\rangle}\mid \gcd{n,m}=1 \right\}}\)

  2. Mostrar que Prime\(_1={\left\{ {\left\langle p\right\rangle}\mid {\left\langle p\right\rangle}\text{ é representação binária de um primo} \right\}}\in \mathsf{P}\)

  3. Mostrar que ModExp\(={\left\{ {\left\langle a,b,c,p\right\rangle}\mid a,b,c,p\in{\mathbb{Z}}\; a^b\equiv c\pmod{p} \right\}}\in \mathsf{P}\)

  4. Mostrar que SPath\(={\left\{ {\left\langle G,a,b,k\right\rangle}\mid G\text{ contém $k$-caminho simples $a$ para $b$} \right\}}\in \mathsf{P}\)

  5. Mostrar que LPath\(={\left\{ {\left\langle G,a,b,k\right\rangle}\mid G \text{ contém caminho simples de $a$ para $b$ de tamanho pelo menos $k$} \right\}}\) é NP-completa.

  6. Mostrar que Double-Sat\(={\left\{ {\left\langle \phi\right\rangle}\mid \phi\text{ tem pelo menos duas atribuições que satisfazem }\phi \right\}}\) é NP-completa.

  7. Mostrar que Half-Clique\(={\left\{ {\left\langle G\right\rangle}\mid G\text{ grafo com subgrafo completo com pelo menos metade dos vértices} \right\}}\) é NP-completo.

Folha de Trabalho 7
  1. Responde, justificando, se são verdadeiras ou falsas as seguintes proposições:

    1. \(2n=\mathcal{O}(n\).

    2. \(n^2=\mathcal{O}(n)\).

    3. \(n^2=\mathcal{O}(n \log n).\)

    4. \(n\log n = \mathcal{O}(n^2).\)

    5. \(3^n=\mathcal{O}(2^n).\)

  2. A seguinte fórmula é satisfazível? \[(x\vee y)\wedge(x\vee\overline{y})\wedge(\overline{x}\vee y)\wedge(\overline{x}\vee\overline{y}).\]

  3. Mostrar que a classe \(P\) é fechada para

    1. reunião,

    2. concatenação,

    3. complemento,

    4. fecho de Kleene.

  4. Mostrar que a classe \(NP\) é fechada para

    1. reunião,

    2. concatenação.

  5. Seja \(CONNECTED=\{\langle G\rangle\mid G\text{ é grafo conexo}\}\). \(Connected\) está em \(P\)?

  6. Seja \(TRIANGLE=\{\langle G\rangle\mid G\text{ contém um }K_3\}\). Mostrar que \(TRIANGLE\in P\).

Folha de Trabalho 6
  1. Se \(A\leq_m B\) e \(B\) é uma linguagem regular, podemos concluir que \(A\) é regular? Porquê?

  2. Mostrar que \(A_{TM}\) não se reduz a \(E_{TM}\). Por outras palavras, mostrar que nenhuma função computável reduz \(A_{TM}\) a \(E_{TM}\).

  3. Mostrar que \(\leq_m\) é transitiva.

  4. Mostrar que são decidíveis as seguintes linguagens.

  5. Mostrar que se \(A\) é reconhecível e \(A\leq_m \overline{A}\), então \(A\) é decidível.

  6. Seja \(C_{CFG}=\{\langle G,k\rangle\mid G \text{ CFG e }\mathcal{L}(G)\text{ tem exactamente }k\text{ palavras, com $k\geq0$ ou $k=\infty$}\}\). Mostrar que \(C_{CFG}\) é decidível.

  7. Seja \(E=\{\langle M\rangle\mid M \text{ é um DFA que aceita alguma palavra com mais $1$'s que $0$'s}\}\). Mostrar que \(E\) é decidível.

  8. Seja \(PAL_{DFA}=\{\langle M\rangle\mid M\text{ é DFA que aceita algum palíndromo}\}\). Mostrar que \(PAL_{DFA}\) é decidível.

  9. Mostrar que uma TM com uma só fita, que não pode escrever na parte da fita que contém o input, só pode decidir linguagens regulares.

Folha de Trabalho 4
  1. Mostrar que a classe da linguagens reconhecíveis é fechada para:

    1. união

    2. intersecção

    3. concatenação

    4. fecho de Kleene

  2. Mostrar que a classe das linguagens decidíveis fechada para:

    1. união

    2. intersecção

    3. concatenação

    4. fecho de Kleene

    5. complementação

  3. Mostrar que são decidíveis as seguintes linguagens.

    1. \(A\varepsilon_{CFG}=\{\langle A\rangle\mid G\text{ é }CFG\wedge \varepsilon\in\mathcal{G}\}\).

    2. \(ALL_{DFA}=\{\langle A\rangle\mid A\text{ é } DFA \wedge \mathcal{L}(A)=\Sigma^\star\}\).

    3. \(S=\{\langle A\rangle \mid A\text{ é }DFA \wedge w\in\mathcal{L}(A)\implies w^R\in\mathcal{L}(A)\}\).

    4. \(PREFIX-FREE_{REX}=\{ \alpha\mid \alpha\in RE \wedge \mathcal{L}(\alpha) \text{ é livre de prefixos} \}\)

  4. Sejam \(A\) e \(B\) duas linguagens disjuntas. Diz-se que \(C\) separa \(A\) de \(B\) se \(A\subseteq C\) e \(B\subseteq\overline{C}\). Mostrar que linguagens disjuntas co-reconhecíveis são separáveis por uma linguagem decidível.

  5. Mostrar que uma linguagem é decidível se e só se existir um enumerador que enumera as suas palavras pela ordem lexicográfica.

  6. Mostrar que a classe das linguagens decidíveis não é fechada para homomorfismos.

  7. Seja \(C\) uma linguagem. Mostrar que \(C\) é reconhecível se e só se existe uma linguagem decidível \(D\) tal que \(C=\{x : \exists y, \langle x,y\rangle\in D\}.\)

Folha de Trabalho 3
  1. Mostra que as seguintes linguagens não são independentes do contexto.

    1. \(\{0^n1^{2n}0^n\mid n\in \}\)

    2. \(\{ww\mid w\in \{0,1\}^\star\}\)

    3. \(\{a^nb^nc^m\mid n\geq 0,\; m\leq n\}\)

    4. \(\{a^ib^jc^k\mid 0\leq i\leq j\leq k\}\)

    5. \(\{0^p\mid p \mbox{ é primo}\}\)

    6. \(\{0^{n^2}\mid n\geq 0\}\)

  2. Em geral as linguagens independentes de contexto não são fechadas para a complementação nem para a intersecção.

    1. Dá um exemplo de duas linguagens \(L_1\) e \(L_2\) independentes de contexto, tais que \(L_1\cap L_2\) não seja independente de contexto.

    2. Dá um exemplo de duas linguagens \(L_1\) e \(L_2\) independentes de contexto, mas não regulares, tais que \(L_1\cap L_2\) seja independente de contexto.

    3. Dá um exemplo duma linguagem \(L_1\) independente de contexto, tal que \(\Sigma^\star\setminus L_1\) não seja independente de contexto.

  3. Constrói máquinas de Turing que aceitem cada uma das seguintes linguagens. Indica as que são independentes de contexto.

    1. \(\{0^n1^m\mid n\leq m\}\)

    2. \(\{a^nb^nc^n\mid n\geq 0\}\)

    3. \(\{1^p01^q01^n\mid p+q=n\}\)

    4. as palavras de \(\{a,b\}^\star\) com mais \(a\)’s que \(b\)’s

    5. \(\star\) \(\{a^{n^2}\mid n\geq 1\}\)

    6. \(\star\) \(\{a^{2^n}\mid n\geq 1\}\)

    7. \(\star\) \(\{a^p\mid \mbox{$p$ primo}\}\)

    8. \(\star\) \(\{ww^r\mid w\in\{a,b\}^\star\}\)

    9. \(\{w@w\mid w\in\{a,b\}^\star\}\)

    10. \(\star\) \(\{ww\mid w\in\{a,b\}^\star\}\)

    11. \(\{x\texttt{c}^n x^R\mid x\in \{\texttt{a},\texttt{b}\}^\star,\;\; |x|=n\}\)

    12. \(\{0^{n}1^m2^{k}3^l\mid n,m,k,l\geq 0,\; n=3k\text{ e } m=l\}\)

    13. \( \{ a^ib^{j}c^k\mid i,j,k\geq 0 \; j=2i \mbox{ e } k=i\} \)

Folha de Trabalho 2
  1. Constrói gramáticas independentes de contexto que gerem as linguagens descritas pelas seguintes expressões regulares:

    1. \(0^\star 1(0+1)^\star\)

    2. \(0^\star1^\star2^\star\)

    3. \((0+1+2)^\star 1(0+1+2)^\star1(0+1+2)^\star0(1+2)^\star \)

    4. \((0+2)^\star(1(0+1+2))^\star\).

  2. Considera a seguinte gramática independente de contexto:

    \[G_1=\{\{E,A,B\},\{ E\rightarrow AAE\mid A\mid \epsilon, A\rightarrow a Ab \mid a Bb, B\rightarrow Bb\mid \epsilon\},\{a,b\},E\}\]

    1. Descreve, justificando, \(L(G_1)\).

    2. Obtém uma gramática que gere \(L(G_1)\setminus \{\epsilon\}\) sem produções \(\epsilon\), sem produções unitárias e sem símbolos inúteis.

    3. Obtém uma gramática equivalente à obtida em forma normal de Chomsky.

  3. Constrói gramáticas independentes de contexto que reconheçam as seguintes linguagens. O alfabeto considerado é \(\Sigma = \{0,1\}\).

    1. O conjunto vazio

    2. \(\{w : \mbox{$w$ contém pelo menos três 1s}\}\)

    3. \(\{w : \mbox{$w$ começa e termina pelo mesmo símbolo}\}\)

    4. \(\{w : \mbox{o comprimento de $w$ é ímpar}\}\)

    5. \(\{w : \mbox{o comprimento de $w$ é ímpar e o símbolo do meio é 0}\}\)

    6. \(\{w : \mbox{$w$ contém mais 1s que 0s}\}\)

    7. \(\{w : w = w^R\}\)

    8. \(\{w : \mbox{$w$ tem duas vezes mais 0s do que 1s}\}\)

    9. O complemento da linguagem \(\{0^n 1^n : n \geq 0 \}\)

    10. \(\{w\in\{0,1\}^{\star} |\) 3 divide a diferença entre o número de 0’s e 1’s em \(w \}\)

    11. \(\{a^{i}b^{j}c^{i} \in\{a,b,c\}^{\star} |\, i\geq 0,\, j\geq 0\}\)

    12. \(\{a^{i}b^{i+j}c^{j} \in\{a,b,c\}^{\star} |\, i\geq 0,\, j\geq 0\}\)

  4. Dada uma gramática em forma normal de Chomsky, mostra por indução sobre \(n\), que todas as árvores de derivação de palavras de tamanho \(n\) têm \(2n-1\) nós interiores.

  5. Supõe que uma gramática independente de contexto \(G\) não tem produções \(\epsilon\). Mostra que:

    Se \(x\in L(G)\), \(\mid x\mid=n\) e \(x\) tem uma derivação em \(m\) passos então \(x\) tem uma árvore de derivação com \(n+m\) nós.

  6. Uma produção-\(A\) é uma produção que tem \(A\) no lado esquerdo. Seja \({ G}=(V,\Sigma,P,S)\) uma GIC, seja \(A\to \alpha_1B\alpha_2\in P\) e sejam \(B\to \beta_1\;\;|\;\;\cdots\;|\;\;\beta_r\) as produções-\(B\). Seja \(G_1=(V,\Sigma,P_1,S)\) a gramática que se obtém substituindo \(A\to\alpha_1B\alpha_2\) em \( G\), por \(A\to \alpha_1\beta_1\alpha_2 \;\;|\;\;\cdots\;|\;\;\alpha_1\beta_r\alpha_2\). Mostra que \(L(G)=L(G_1)\).

  7. Seja \(\mathtt{B}\subseteq \{\mathtt{a},\mathtt{b}\}^\star\) constituída pelas palavras em que o número de \(\mathtt{b}\)s é igual ao número de blocos de \(\mathtt{a}\)s consecutivos de comprimento maior ou igual a dois.

    Por exemplo \(\mathtt{aaababaaa}, \mathtt{baaabaaa}\) são palavras de \(\mathtt{B}\) e \(\mathtt{aaabab}\) não pertence a \(\mathtt{B}\).

    1. Descreve uma gramática independente de contexto que gere \(\mathtt{B}\)[gra].

    2. Converte a gramática obtida para a forma normal de Chomsky e apresenta para esta gramática uma árvore de derivação para \(\mathtt{aaab}\).

  8. Seja \(D\) a linguagem de alfabeto \(\{\mathtt{0},\mathtt{1},\mathtt{,},\mathtt{)},\mathtt{(},\mathtt{]},\mathtt{[}\}\), das palavras que são listas de listas de tuplos de 0s e de 1s, i,e,

    • um tuplo é uma sequência, eventualmente vazia, de 0s e 1s, separados por vírgulas , e entre parêntisis curvos, p.e \((\mathtt{1,0,0,1})\). Tuplos com um 0 ou um 1 não podem ter vírgulas e não podem terminar em vírgulas.

    • uma lista de tuplos é uma sequência, eventualmente vazia, de tuplos separados por vírgulas , e entre parêntisis rectos, p.e \([(\mathtt{1,0,0,1}),(),(\mathtt{0})]\). Se só tiver um tuplo não pode ter vírgulas e não pode terminar em vírgulas.

    • uma lista de listas é, uma sequência, eventualmente vazia, de listas separadas por vírgulas , e entre parêntisis rectos, p.e \([[(\mathtt{1,0,0,1}),(),(\mathtt{0})],[(\mathtt{0})]]\). Se só tiver uma lista não pode ter vírgulas e não pode terminar em vírgulas.

    Por exemplo, \([[(\mathtt{1},\mathtt{0},\mathtt{1}),(\mathtt{0})],[(\mathtt{0},\mathtt{0},\mathtt{0}),(\mathtt{1},\mathtt{0}),(\mathtt{0},\mathtt{1})]]\in D\)

    1. Determina uma gramática independente de contexto que gere \(D\).

    2. Converte a gramática obtida para a forma normal de Chomsky. Para esta gramática apresenta uma árvore de derivação para a palavra \([[(\mathtt{1,0}),()]]\).

  9. Dada a gramática \[\begin{aligned} S&\rightarrow& aB\mid bA\\ A&\rightarrow& a\mid aS \mid bAA\\ B&\rightarrow& b\mid bS\mid aBB\end{aligned}\] escrever uma árvore de derivação para a palavra \(aaabbabbba\).

  10. Escrever a CFG seguinte na sua Forma Normal de Chomsky (CNF) \[\begin{aligned} S &\rightarrow& AB \mid CA\\ B &\rightarrow& BC | AB\\ A &\rightarrow& a\\ C &\rightarrow& aB\mid b.\end{aligned}\]

  11. Escreve uma CFG que reconheça a linguagem das palavras de alfabeto \(\{0,1\}\) que o número de \(0\)s é o mesmo que o de \(1\)s.

    A gramática que escreveste é não ambígua? Consegues escrever uma que o seja?

Folha de Trabalho 1
  1. Para cada uma das seguintes linguagens, encontra um DFA que as represente:

    1. \(\{w\in \{0,1\}^\star \mid w_{(2)}\equiv 3 \pmod{4}\}\)

    2. \(\{w\in\{a,b\}^\star\mid w\text{ tem como sufixo }a\text{ ou }bb\}\)

    3. \(\{w\in\{a,b\}^\star\mid w\text{ não tem como sufixo }a\text{ ou }bb\}\)

    4. O conjunto das palavras de alfabelto \(\{a,b\}\) que não tem \(aaa\) como subpalavra.

  2. Para cada uma das das linguagens seguintes indica, justificando, se se trata de uma linguagem regular, ou não.

    1. \(\{ww\mid w\in \{0,1\}^\star\}\)

    2. Seja \(L\) uma linguagem regular, \(\{ww'\mid w,w'\in L\}\)

    3. \(\{a^nb^n\mid n\in \mathbb{N}\}\)

    4. \(\{a^{n^2}\mid n\in\mathbb{N}\}\)

    5. Seja \(L\) uma linguagem regular, \(\{w\mid ww\in L\}\)

    6. \(\{a^{2^n}\mid n\in \mathbb{N}\}\)

    7. A linguagem \(\{w\mid \exists i\; rot_i(w)\in L\}\), em que \(L\) é uma linguagem regular e denotamos por \(rot_i(w)\) a permutação circular de ordem \(i\) da palavra \(w\) (\(rot_0(w)=w, \forall w\), \(rot_1(abc)=bca=rot_4(abc)\))

    8. \(\{a^nb^m\mid m\neq n\}\)

    9. Seja \(L\) uma linguagem regular, \(\{w\mid w^R\in L\}\)

    10. A linguagem dos palíndromos.

    11. O conjunto das palavras de alfabeto \(\{a,b\}\) que tem o mesmo número de \(a\) e de \(b\).

    12. \(\{0^p\mid \text{ com $p$ primo}\}\)

    13. \(\{xx^Rw\mid x,w\in \{a,b\}^\star\}\)