Exercícios
Folha de Trabalho 1
27 de Fevereiro e 1 de Março
Para cada uma das seguintes linguagens, encontra um DFA que as represente:
\(\{w\in \{0,1\}^\star \mid w_{(2)}\equiv 3 \pmod{4}\}\)
\(\{w\in\{a,b\}^\star\mid w\text{ tem como sufixo }a\text{ ou }bb\}\)
\(\{w\in\{a,b\}^\star\mid w\text{ não tem como sufixo }a\text{ ou }bb\}\)
O conjunto das palavras de alfabelto \(\{a,b\}\) que não tem \(aaa\) como subpalavra.
Para cada uma das das linguagens seguintes indica, justificando, se se trata de uma linguagem regular, ou não.
\(\{ww\mid w\in \{0,1\}^\star\}\)
Seja \(L\) uma linguagem regular, \(\{ww'\mid w,w'\in L\}\)
\(\{a^nb^n\mid n\in \mathbb{N}\}\)
\(\{a^{n^2}\mid n\in\mathbb{N}\}\)
Seja \(L\) uma linguagem regular, \(\{w\mid ww\in L\}\)
\(\{a^{2^n}\mid n\in \mathbb{N}\}\)
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)\))
\(\{a^nb^m\mid m\neq n\}\)
Seja \(L\) uma linguagem regular, \(\{w\mid w^R\in L\}\)
A linguagem dos palíndromos.
O conjunto das palavras de alfabeto \(\{a,b\}\) que tem o mesmo número de \(a\) e de \(b\).
\(\{0^p\mid \text{ com $p$ primo}\}\)
\(\{xx^Rw\mid x,w\in \{a,b\}^\star\}\)
Folha de Trabalho 2
06 e 08 de Março
Constrói gramáticas independentes de contexto que gerem as linguagens descritas pelas seguintes expressões regulares:
\(0^\star 1(0+1)^\star\)
\(0^\star1^\star2^\star\)
\((0+1+2)^\star 1(0+1+2)^\star1(0+1+2)^\star0(1+2)^\star \)
\((0+2)^\star(1(0+1+2))^\star\).
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\}\]
Descreve, justificando, \(L(G_1)\).
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.
Obtém uma gramática equivalente à obtida em forma normal de Chomsky.
Constrói gramáticas independentes de contexto que reconheçam as seguintes linguagens. O alfabeto considerado é \(\Sigma = \{0,1\}\).
O conjunto vazio
\(\{w : \mbox{$w$ contém pelo menos três 1s}\}\)
\(\{w : \mbox{$w$ começa e termina pelo mesmo símbolo}\}\)
\(\{w : \mbox{o comprimento de $w$ é ímpar}\}\)
\(\{w : \mbox{o comprimento de $w$ é ímpar e o símbolo do meio é 0}\}\)
\(\{w : \mbox{$w$ contém mais 1s que 0s}\}\)
\(\{w : w = w^R\}\)
\(\{w : \mbox{$w$ tem duas vezes mais 0s do que 1s}\}\)
O complemento da linguagem \(\{0^n 1^n : n \geq 0 \}\)
\(\{w\in\{0,1\}^{\star} |\) 3 divide a diferença entre o número de 0’s e 1’s em \(w \}\)
\(\{a^{i}b^{j}c^{i} \in\{a,b,c\}^{\star} |\, i\geq 0,\, j\geq 0\}\)
\(\{a^{i}b^{i+j}c^{j} \in\{a,b,c\}^{\star} |\, i\geq 0,\, j\geq 0\}\)
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.
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.
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)\).
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}\).
Descreve uma gramática independente de contexto que gere \(\mathtt{B}\)[gra].
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}\).
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
0
s e de1
s, i,e,um
tuplo
é uma sequência, eventualmente vazia, de0
s e1
s, separados por vírgulas,
e entre parêntisis curvos, p.e \((\mathtt{1,0,0,1})\). Tuplos com um0
ou um1
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\)
Determina uma gramática independente de contexto que gere \(D\).
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}),()]]\).
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\).
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}\]
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 3
13 e 15 de Março
Mostra que as seguintes linguagens não são independentes do contexto.
\(\{0^n1^{2n}0^n\mid n\in N \}\)
\(\{ww\mid w\in \{0,1\}^\star\}\)
\(\{a^nb^nc^m\mid n\geq 0,\; m\leq n\}\)
\(\{a^ib^jc^k\mid 0\leq i\leq j\leq k\}\)
\(\{0^p\mid p \mbox{ é primo}\}\)
\(\{0^{n^2}\mid n\geq 0\}\)
Em geral as linguagens independentes de contexto não são fechadas para a complementação nem para a intersecção.
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.
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.
Dá um exemplo duma linguagem \(L_1\) independente de contexto, tal que \(\Sigma^\star\setminus L_1\) não seja independente de contexto.
Constrói máquinas de Turing que aceitem cada uma das seguintes linguagens. Indica as que são independentes de contexto.
\(\{0^n1^m\mid n\leq m\}\)
\(\{a^nb^nc^n\mid n\geq 0\}\)
\(\{1^p01^q01^n\mid p+q=n\}\)
as palavras de \(\{a,b\}^\star\) com mais \(a\)’s que \(b\)’s
\(\star\) \(\{a^{n^2}\mid n\geq 1\}\)
\(\star\) \(\{a^{2^n}\mid n\geq 1\}\)
\(\star\) \(\{a^p\mid \mbox{$p$ primo}\}\)
\(\star\) \(\{ww^r\mid w\in\{a,b\}^\star\}\)
\(\{w@w\mid w\in\{a,b\}^\star\}\)
\(\star\) \(\{ww\mid w\in\{a,b\}^\star\}\)
\(\{x\texttt{c}^n x^R\mid x\in \{\texttt{a},\texttt{b}\}^\star,\;\; |x|=n\}\)
\(\{0^{n}1^m2^{k}3^l\mid n,m,k,l\geq 0,\; n=3k\text{ e } m=l\}\)
\( \{ a^ib^{j}c^k\mid i,j,k\geq 0 \; j=2i \mbox{ e } k=i\} \)
Folha de Trabalho 4
20 e 22 de Março
Mostrar que a classe de linguagens reconhecíveis é fechada para:
União
Intersecção
Concatenação
Fecho de Kleene
Mostrar que a classe das linguagens decidíveis é fechada para:
União
Intersecção
Concatenação
Fecho de Kleene
Complementação
Mostrar que são decidíveis as seguintes linguagens.
\(A\varepsilon_{CFG}=\{\langle A\rangle\mid G\text{ é } CFG \wedge \varepsilon\in\mathcal{L}(G)\}\)
\(ALL_{DFA}=\{\langle A\rangle\mid A\text{ é } DFA \wedge \mathcal{L}(A)=\Sigma^\star\}\)
\((S=\{\langle A\rangle \mid A\text{ é }DFA \wedge w\in\mathcal{L}(A)\implies w^R\in \mathcal{L}(A)\}\)
\(PREFIX-FREE_{REX}=\{\alpha \mid \alpha\in RE \wedge \mathcal{L}(\alpha) \text{ é livre de prefixos}\}\)
Sejam \(A\) e \(B\) duas linguagens disjuntas; diz-se que \(C\)) separa \\(A\) de \(B\) se \(A\subseteq C \wedge B\subseteq\overline{C}\). Mostrar que linguagens disjuntas co-reconhecíveis são separáveis por uma linguagem decidível.
Mostrar que uma linguagem é decidível se e só se existir um enumerador que enuméra as suas palávras pela ordem hierárquica.
Mostrar que a classe das linguagens decidíveis não é fechada para homomorfismos.
Seja \(C\) uma linguagem. Mostrar que \(C\) é reconhecível se e só se existe uma linguagem decidível \(D\) tal que \(C=\{x \mid \exists y, \langle x,y\rangle\in D\}\).
Folha de Trabalho 5
03 e 05 de Abril
Mostrar que \(EQ_{DFA}\) se pode decidir tentando todas as palavras até um dado tamanho. Qual esse tamanho?
Mostrar que \(S=\{\langle M\rangle\mid M\; DFA\; w\in\mathcal{L}(M)\implies w^R\in\mathcal{L}(M)\}\) é decidível.
Mostrar que \(A=\{\langle R\rangle\mid R\text{ expressão regular com $111$ como infixo}\}\) é decidível.
Mostrar que \(U=\{\langle G\rangle\mid G\; CFG\;\wedge\; \exists n>0\; 1^n\in\mathcal{L}(G)\}\) é decidível.
Mostrar que \(V=\{\langle G\rangle\mid G\; CFG\;\wedge\; \mathcal{L}(1^\star)\subseteq\mathcal{L}(G)\}\) é decidível.
Mostrar que \(B=\{\langle R, R'\rangle\mid R,R'\text{ expressões regulares com } \mathcal{L}(R)\subseteq\mathcal{L}(R')\}\) é decidível.
Mostrar que \(X=\{\langle G\rangle\mid G\; CFG\;\wedge\; \mathcal{L}(G)\text{ é infinita }\}\) é decidível.
Folha de Trabalho #6
Responde, justificando, se são verdadeiras ou falsas as seguintes proposições:
- \(2n= \mathcal{O}(n)\)
- \(n^2=\mathcal{O}(n)\)
- \(n^2=\mathcal{O}(n \log n)\)
- \(n\log n = \mathcal{O}(n^2)\)
- \(3^n=\mathcal{O}(2^n)\)
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})\]
- Mostrar que a classe \(P\) é fechada para:
- reunião
- concatenação
- complemento
- fecho de Kleene
- Mostrar que a classe \(NP\) é fechada para:
- reunião
- concatenação
Seja \(\mathsf{Connected}={\langle G\rangle\mid G\text{ é grafo conexo}}\). \(\mathsf{Connected}\) está em \(P\)?
Seja \(\mathsf{Triangle}={\langle G\rangle\mid G\text{ contém um }K_3}\). Mostrar que \(\mathsf{Triangle}\in P\).
Folha de trabalho #7
Mostrar que \(\mathsf{ALL}_{DFA}\in P\).
Mostrar que \(\mathsf{EQ}_{DFA} está em P\).
Mostrar que \(\mathsf{ISO}_{Graph} \in NP\).
Mostrar que \(2\mathsf{SAT}\in P\).
Mostrar que \(\mathsf{ModExp}=\{\langle a,b,c,p\rangle \mid a^b\equiv c\pmod{p}\}\) está em \(P\).
Mostrar que \(NP\) é fechado para o fecho de Kleene
Mostrar que se \(P=NP\) então \(\forall A\in P, A\neq\emptyset\wedge A\neq \Sigma^\star \Rightarrow A\) é \(NP\) completa.
Última modificação: 19/02/2025