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.

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

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\).

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.

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

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

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

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}),()]]\).

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?

Mostra que as seguintes linguagens não são independentes do contexto.

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

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

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.

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