A Linguagem Formais
Por: jair.ntj • 29/5/2017 • Dissertação • 493 Palavras (2 Páginas) • 176 Visualizações
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.
...