CENTRO UNIVERSITÁRIO DE BRASÍLIA - UniCEUB
Faculdade de Ciências Exatas e Tecnologia - FACET
Curso de Bacharelado em Ciência da Computação
Disciplina: TEORIA DA COMPUTAÇÃO
Professor: Luis Alberto Martins Palhares de Melo
Exercícios 01
1a Questão Considere a gramática abaixo que gera sentenças da linguagem L onde
L = { w | w = 0m1, m ≥ 1 }.
1 a) Qual a sequência de derivação que pode ser executada para que se gere a sentença w = 0001 ?
1 b) A linguagem gerada pela gramática apresenta uma quantidade finita ou infinita de sentenças ?
1 c) A gramática é regular (linear ou Tipo 3) ? Caso a gramática não seja linear, indique as regras de
produção que não apresentam o “formato” de uma regra de produção de gramática regular.
1 d) Codifique no programa JFLAP a gramática acima.
Obs.: executar o programa JFLAP ⇒ opção Grammar ⇒ editar as regras de produção da gramática
1 e) Testar a gramática verificando se a mesma gera a sentença w = 00001
1 f) Testar a gramática verificando se a mesma gera a sentença w = 000101
Obs.: Para testar no JFLAP: opção Input ⇒ Brute Force Parse ⇒ Derivation Table (ou Noninverted
tree) ⇒ Start ⇒ Step (até derivar)
CENTRO UNIVERSITÁRIO DE BRASÍLIA - UniCEUB
Faculdade de Ciências Exatas e Tecnologia - FACET
Curso de Bacharelado em Ciência da Computação
Disciplina: TEORIA DA COMPUTAÇÃO
Professor: Luis Alberto Martins Palhares de Melo
2a Questão Considere a gramática abaixo, que gera sentenças (“cromossomos”) da “Linguagem de
Cromossomos Medianos”.
G = { V, T, P, S };
V = {S, A, B, D, H, X, J, E, F, W, K, G, R, L, Y, M, N}; T = { a, b, c, d, e }
P:
(1) S → AA
(6) D → d
(2) A → cB
(7) F → b
(3) B → FBE
(8) E → b
(4)B→
→ HDJ
(9) H → a
(5) D → FDE
(10) J → a
2 a) Qual a sequência de derivação que pode ser executada para que se gere a sentença (cromossomo)
w = cadacada ?
2 b) Qual a sequência de derivação que pode ser executada para que se gere a sentença (cromossomo)
w = cbabdbabcbabdbab ?
2 c) Qual a sequência de derivação que pode ser executada para que se gere a sentença (cromossomo)
w = bebabcba ?
2 d) A linguagem gerada pela gramática apresenta uma quantidade finita ou infinita de sentenças
(cromossomos) ?
2 e) A gramática é regular (linear ou Tipo 3) ? Caso a gramática não seja linear, indique as regras de
produção que não apresentam o “formato” de uma regra de produção de gramática regular.
CENTRO UNIVERSITÁRIO DE BRASÍLIA - UniCEUB
Faculdade de Ciências Exatas e Tecnologia - FACET
Curso de Bacharelado em Ciência da Computação
Disciplina: TEORIA DA COMPUTAÇÃO
Professor: Luis Alberto Martins Palhares de Melo
3a Questão
1) Codifique no programa JFLAP a gramática que gera sentenças (“cromossomos”) da “Linguagem de
Cromossomos Medianos” da 2a Questão.
Obs.: executar o programa JFLAP ⇒ opção Grammar ⇒ editar as regras de produção da gramática
2) Testar a gramática verificando se a mesma gera a sentença w = cadacada
3) Testar a gramática verificando se a mesma gera a sentença w = bebabcba
Obs.: Para testar no JFLAP: opção Input ⇒ Brute Force Parse ⇒ Derivation Table (ou Noninverted
tree) ⇒ Start ⇒ Step (até derivar)
Curiosidade: Se você tentar testar a gramática para a sentença w = cbabdbabcbabdbab
(da item 2b da Questão 2), o JFLAP não conseguirá derivar, apesar de ser possível a
derivação (caso tenha feito corretamente o exercício 2b, você deve ter conseguido
apresentar a sequência de derivação). Isto ocorre devido a lógica implementada pelo
programador do JFLAP.