A Linguagem Formais

Atividade Extra-Classe (ER e Gramatica)

Parte A:

1.a) {a, aa, aaa, aaaa...}

Todas as palavras de ‘a’ geradas tal que a^n  e n≥1.

b) {aa, aaa, aaaa...}

Todas as palavras de ‘a’ geradas tal que a^n  e n>1.

c) {2, 012, 02, 12, 112, 002...}

Todas as palavras de ‘012’ geradas tal que 0^n 1^m2  e n, m ≥1.

d) {aa, aab, aaab, b...}

Todas as palavras de ‘aabb’ geradas tal que a^n b e n≥0.

e) {ab, aab, abab, bbab, ba, aba, bba, aaba, a, b}

Todas as palavras de ‘ab’ geradas tal que a^n b^m ba e n, m≥0.

2.a) {ab, aab, abb, aabb...}        

a(a | b)* b

b) {aaa, aaaaaa, aaaaaaaaa...}                   

(aaa)+

c) {b, bb, bbb}                   

(b | bb | bbb)

d) {aaa, aaab, aaabb...}                

aaab*

3) A e C

A- baa Є a* b* a* b* = {Ɛ, ab, aba, aabb, baa ...}

a* b* ᴖ c* d* = 0 = { Ɛ, a, b, c, d, ...}

4) F / F/ V/ F/ F

5) (0| 1 | 3 |5 |7 |9)+

6) (0 | 1)+

Parte B

1.a) abb

{X → aX → bX → b } É gerada pela gramática.

b) aba

{X → aX → bX → aX} Não é gerada pela gramática.

c) ba

{X → bX → aX} Não é gerada pela gramática.

d) aaab

{X → aX → aX → aX → b} É gerada pela gramática.

e) aaaab

{X → aX → aX → aX → aX → b} É gerada pela gramática.

2.a) 010101

{A →0A → .} Não é gerada.

b) 00110

{A → 0A → 00A → 00B → 001B →.} Não é gerada.

c)  110

{B → 1B → 11B. } Não é gerada.

d) 00111

{A → 0A → 00A →00B → 001B → 0011B → 00111} É gerada.

4.a) 0111

{S → OB → 01D → 011B → 0111B → 0111Ɛ → 0111}

b) 1101

{S  → 1C → 11S → 110C → 1101C → 1101Ɛ → 1101}

c)  01110

{S → 0C → 01S → 011C → 0111S → 01110C → 01110Ɛ → 01110}

d) 10011

{S → 1C → 10D → 100C → 1001S → 10011C → 10011Ɛ → 10011}

5.a)  0 + 1 Não é gerada.