Teoria Da Computação

1. O que é alfabeto?

2. Defina o conceito de cadeia.

3. Defina o conceito de linguagem e mostre um exemplo.

4. O que é fechamento de um alfabeto?

5. Como se pode descrever uma linguagem formal?

6. Descreva sobre as aplicações de LFA (Linguagens Formais e Autômatos).

7. Defina o conceito de subpalavra.

8. Prove que se uma cadeia x é prefixo de uma cadeia y e y também é prefixo de x, então x e y

são iguais.

9. Prove que se uma cadeia x é prefixo de uma cadeia y e y é prefixo de uma cadeia z, então x

é prefixo de z.

10. Dados L1={a, ab} e L2={l, a, ba}, linguagens sobre o alfabeto {a, b}, determine:

a) L1∩ L2

b) L1 U L2

c) L1 – L2

d) L2 – L1

e) L1.L2

11. Exemplifique gramática livre de contexto, gramática sensível ao contexto e gramática regular.

12. Dadas as seguintes gramáticas:

a. Descreva qual a linguagem gerada por G1.

b. Descreva qual a linguagem gerada por G3.

c. Mostre a derivação de uma sentença através de cada gramática acima.

d. Mostre a derivação da sentença abbabb a partir de G1 e G3, isto é, a partir

das gramáticas G1 e G3 tente validar a sentença abbabb.

e. A partir da gramática G2 faça a derivação e tente validar as

seguintes strings/sentenças: lnnnnl, lln, l, lllllnnn.

13. Construa uma gramática livre de contexto que gere a linguagem:

L = {0 i 1 j 2 k | i, j, k > 0}

14. Dadas as seguintes gramáticas:

a) Descreva qual a linguagem gerada por G1.

b) Descreva qual a linguagem gerada por G2.

c) Descreva qual a linguagem gerada por G3.

d) Verifique se a cadeia abaabb pertence à linguagem L(G1)

e) Verifique se a cadeia ababb pertence à linguagem L(G1)

f) Verifique se a cadeia aabaa pertence à linguagem L(G2)

g) Verifique se a cadeia aaba pertence à linguagem L(G2)

h) Verifique se a cadeia acaca pertence à linguagem L(G3)