Exercícios de Exame

Sim. A expressão regular que representa o DFA mínimo é $(01)^*$. Como o DFA mínimo se obtém por técnicas provadas que transformam qualquer ε-NFA num DFA equivalente e depois num DFA mínimo, e a expressão regular foi obtida por outra técnica provada (eliminação de estados), as duas expressões são equivalentes, isto é, representam a mesma linguagem.

Dois procedimentos correctos aplicados à mesma linguagem não podem dar resultados diferentes: ambos preservam a linguagem reconhecida. Assim, se o DFA mínimo gera $(01)^*$, a expressão por eliminação de estados tem de gerar a mesma linguagem.

Hipótese: $S_n$: as palavras dadas por $0101(01)^n$, com $n\geq0$, pertencem a $(01)^*$. Caso de base: a palavra mais curta é $0101=(01)^2$, que pertence a $(01)^*$. Passo indutivo: $0101(01)^{n+1}=0101(01)^n(01)$; por hipótese, $0101(01)^n\in(01)^*$, e como $(01)^*$ é fechada para a concatenação, a concatenação com $(01)$ continua em $(01)^*$. Logo todas as palavras $0101(01)^n$ pertencem a $(01)^*$.

Como $0101=(01)^2$, cada palavra $0101(01)^n$ é $(01)^{n+2}$, claramente uma palavra de $(01)^*$. A prova por indução formaliza este facto: o caso de base cobre $n=0$ e o passo mostra que acrescentar um bloco $(01)$ preserva a pertença.

Sim, são equivalentes. Pode provar-se convertendo $R^*SU^*(TR^*SU^*)^*$ num DFA (expressão $\to$ ε-NFA $\to$ DFA) e comparando-o com o DFA do autómato generalizado: se os estados iniciais forem equivalentes (indistinguíveis pela tabela de estados distinguíveis), as duas expressões são equivalentes. Alternativamente, constrói-se o produto cartesiano dos dois DFA e verifica-se que ambas as subtrações dão a linguagem vazia, ou prova-se por indução que $L(R^*SU^*(TR^*SU^*)^*)$ é a linguagem do autómato.

Ambas as expressões descrevem percursos no mesmo autómato generalizado: ciclos no estado inicial ($R$), um avanço $S$ seguido de ciclos $U^*$, e repetições do bloco $TR^*SU^*$. A equivalência prova-se pelos métodos padrão de equivalência de autómatos, que são completos.

$L(G)=\{a^k b^l c^m\mid m=k+l,\ k,l,m\geq0\}$.

A produção de $S$ gera $k$ letras $a$ à esquerda e $k$ letras $c$ à direita, com um bloco $B$ no meio. Por sua vez, $B$ gera $l$ letras $b$ à esquerda e $l$ letras $c$ à direita. No total, o número de $c$ é $m=k+l$, pelo que a linguagem é exatamente $\{a^k b^l c^m\mid m=k+l\}$.

A gramática não é ambígua, pois não é possível derivar duas árvores sintáticas diferentes para a mesma palavra de $L(G)$.

A primeira produção do símbolo inicial $S$ deriva recursivamente um $a$ à esquerda e um $c$ à direita, e deriva $B$ para o substring do meio; em $B$, a primeira produção deriva um $b$ à esquerda e um $c$ à direita, ou termina com $\varepsilon$. Como só há uma maneira de acrescentar o par $a,c$ e depois o par $b,c$, não há mais do que uma árvore sintática por palavra.

Uma gramática para $L_1$ é $S\to aSa\mid B$, $B\to bBa\mid\varepsilon$.

A regra $S\to aSa$ acrescenta um $a$ no início e um $a$ no fim (contribuindo $k$ de cada lado), e $B\to bBa$ acrescenta um $b$ no início e um $a$ no fim (contribuindo $l$ $b$ e $l$ $a$ finais). No total, o número de $a$ finais é $m=k+l$, como se pretende.

Prova por indução no tamanho de $w$, para todo $w\in L_2$. Caso de base: $|w|=0$, logo $w=\varepsilon$, e $S\Rightarrow T\Rightarrow\varepsilon$. Passo indutivo: seja $w\in L_2$ com derivação em $G_2$ e $|w|=n$; a palavra seguinte $v$, de tamanho $n+2$, pode formar-se de duas maneiras: (i) $v$ só com $c$ e $d$ (ou $w=\varepsilon$), e $v=cwd$, pois $S\Rightarrow T\Rightarrow cTd\Rightarrow^* cwd$; (ii) $v=awb$, pois $S\Rightarrow aSb\Rightarrow^* awb$. Assim, as palavras de $L_2$ são reconhecidas por $G_2$.

Cada palavra de $L_2$ obtém-se a partir de $\varepsilon$ aplicando repetidamente um par exterior $a\ldots b$ (regra de $S$) ou um par interior $c\ldots d$ (regra de $T$). A indução cobre exatamente estas duas possibilidades de crescimento.

Uma possível MT é $M=(\{s_0,s_1,s_2,s_3,s_4,s_5,s_6,s_f\},\{a,b,c\},\{a,b,c,B\},\delta,s_0,B,\{s_f\})$, com $\delta$ dada pela tabela: $s_0$: em $a\to(s_1,B,R)$, em $b\to(s_4,B,R)$; $s_1$: em $a\to(s_2,B,R)$; $s_2$: em $a\to(s_3,B,R)$; $s_3$: em $a\to(s_1,B,R)$, em $b\to(s_4,B,R)$; $s_4$: em $c\to(s_5,B,R)$, em $B\to(s_f,B,R)$; $s_5$: em $c\to(s_6,B,R)$; $s_6$: em $c\to(s_5,B,R)$, em $B\to(s_f,B,L)$; $s_f$: sem transições.

Os estados $s_0,s_1,s_2,s_3$ varrem os $a$ em ciclo de três ($s_0\to s_1\to s_2\to s_3\to s_1$), garantindo que o número de $a$ é múltiplo de 3; o $b$ leva a $s_4$. Depois, $s_4,s_5,s_6$ varrem os $c$ em ciclo de dois ($s_4\to s_5\to s_6\to s_5$), garantindo que o número de $c$ é par. Se a fita chegar ao branco nesse padrão, a máquina aceita em $s_f$; caso contrário (como $aaabc$, com um único $c$) não há transição e rejeita.

$s_0aaab\vdash s_1aab\vdash s_2ab\vdash 1s_3b\vdash s_4B\vdash s_fB$.

Aplicando a tabela: $s_0$ com $a$ escreve $B$ e vai para $s_1$ ($s_1aab$); $s_1$ com $a\to s_2$ ($s_2ab$); $s_2$ com $a\to s_3$ ($1s_3b$); $s_3$ com $b\to(s_4,B,R)$ ($s_4B$); $s_4$ com $B\to(s_f,B,R)$ ($s_fB$). A máquina aceita, pois atinge o estado final.

Altera-se $(s_1,a)$ para $(s_3,B,R)$ e remove-se o estado $s_2$. Assim, os $a$ são varridos em ciclo de dois ($s_0\to s_1\to s_3\to s_1$), o que corresponde a $a^{2m}$.

Na MT original, o ciclo $s_0\to s_1\to s_2\to s_3\to s_1$ conta os $a$ de três em três. Para passar a contar de dois em dois, basta que $s_1$ volte diretamente a $s_3$, eliminando $s_2$; o resto da máquina (o $b$ e os $c$ pares) permanece inalterado.

Falsa. Contraexemplo: se a LR for uma linguagem finita, a subtração resulta noutra linguagem finita, e toda a linguagem finita é regular. Outro contraexemplo: com $L_1=ab^+(0+1)^*$ (regular) e $L_2=\{c^nd^{n+1}ab\mid n\geq0\}$ (não regular), tem-se $L_1-L_2=(0+1)^*$, que é regular.

A subtração não preserva a não-regularidade. Se a LR tem um número finito de palavras em comum com a LNR, o resultado pode ser finito (logo regular), e mesmo que haja sobreposição infinita o resultado pode continuar regular.

Falsa. Para uma gramática ser ambígua, as duas derivações diferentes têm de ser ambas à esquerda ou ambas à direita. Numa gramática não ambígua podem existir duas derivações diferentes, uma à esquerda e outra à direita, que conduzem à mesma árvore sintática.

A ambiguidade mede a existência de duas árvores sintáticas distintas, e duas árvores distintas equivalem a duas derivações à esquerda diferentes (ou, equivalentemente, duas à direita). Duas derivações genéricas diferentes não bastam.

Falsa. $L_1$ e/ou $L_2$ podem ser linguagens recursivamente enumeráveis (não decidíveis) cuja interseção é decidível; por exemplo, se a interseção for o conjunto vazio, que é uma linguagem decidível.

A decidibilidade não é hereditária para os operandos de uma interseção. O conjunto vazio é decidível, pelo que duas linguagens não decidíveis podem ter interseção vazia e, ainda assim, a interseção ser decidível.

Verdadeira. Como $w$ representa qualquer palavra sobre $\{0,1\}$ e $2^n$ pode ser 1 (quando $n=0$), $L$ é a linguagem de todas as palavras sobre $\{0,1\}$, que se representa pela expressão regular $(0+1)^*$, sendo assim uma LR.

O expoente $2^n$ percorre 1, 2, 4, 8, ..., incluindo o valor 1. Para $n=0$, $w^{2^0}=w^1=w$, com $w$ arbitrário em $\{0,1\}^*$. Logo $L=\{0,1\}^*$, que é regular.

Falsa. Se as linguagens são represented por GLC, são ambas livres de contexto. A interseção de duas CFL não é uma propriedade de fecho das CFL. Exemplo: $L_1=\{a^nb^nc^m\mid m,n\geq0\}$ e $L_2=\{a^nb^mc^m\mid m,n\geq0\}$; então $L_1\cap L_2=\{a^nb^nc^n\mid n\geq0\}$, que não é uma CFL e, portanto, não pode ser representada por uma GLC.

As CFL são fechadas para a unión, a concatenação e a estrela, mas não para a interseção nem para o complemento. O exemplo clássico $a^nb^nc^n$ mostra que a interseção de duas CFL pode cair fora da classe.

Falsa. Contraexemplo: seja $L_1$ uma linguagem não decidível sobre $\{0,1\}$ e $L_2=\{0,1\}\cup L_1$. $L_2$ continua não decidível, mas $L_2^*=\{0,1\}^*$, que é decidível. Logo $L^*$ decidível não implica $L$ decidível.

A operação estrela pode "absorver" a parte não decidível: se $L$ já contém todos os símbolos do alfabeto, $L^*$ é todo o $\Sigma^*$, que é decidível, independentemente de $L$ ser ou não decidível.