Teoria da computação

Universidade Católica de Petrópolis

Teoria da computação

26. Mostre que, se A e B são conjuntos enumeráveis, então A xB também é enumerável. n( (a, b) ) = g(nA (a), nB (b))

33. Considere a gsc G com nãoterminais S e T, terminais a, b e c, símbolo inicial S e regras
S aSa | bSb | T
T cT | c
(Note que G é também uma glc.) Seja x = aabbb. Utiliza o algoritmo apresentado na demonstração de que toda lsc é um conjunto recursivo para determinar se x Î L(G).

{ S, aSa, bSb, T, aaSaa, abSba, aTa, baSab, bbSbb, bTb, cT, c, aaTaa, abTba, acTa, aca, baTab, bbTbb, bcTb, bcb, ccT, cc, aacaa, abcba, accTa, acca, bacab, bbcbb, bccTb, bccb, cccT, ccc, accca, bcccb, ccccT, cccc, ccccc }

30. Mostre que a linguagem I = { e } é o elemento neutro (identidade) da concatenação de linguagens, ou seja, para qualquer linguagem L, L °I = I °L = L.
L = {0, 11}
L0 = { e }
L1 = L ° L0 = { e } ° {0, 11} = {0, 11}
L2 = L ° L1 = {0, 11} ° {0, 11} = {00, 011, 110, 1111}
L3 = L ° L2 = {0, 11} ° {00, 011, 110, 1111} == {000, 0011, 0110, 01111, 1100, 11011, 11110, 111111}

13. Prove ou des-prove:
A concatenação de dois conjuntos recursivamente enumeráveis é sempre recursivamente enumerável.
Se um conjunto A e seu complemento A são ambos recursivamente enumeráveis, então A (e o complemento A) são ambos recursivos
17. A classe dos conjuntos recursivos é fechada para a operação de complemento?
A classe dos conjuntos recursivamente enumeráveis é fechada para as operações de união e de interseção.
5. Mostre que a união de linguagens regulares é regular mostrando como construir uma gramática regular para a linguagem LÈM, a partir de gramáticas regulares de L e de M.
Sejam A e B conjuntos r.e. e sejam a e b procedimentos que enumeram os elementos de A e de B, respectivamente. Um procedimento g que enumera os elementos de AU B executa a e b em paralelo é:
Os elementos emitidos por g são exatamente os elementos de A e os elementos de B, ou
seja,