CENTRO UNIVERSITÁRIO DE BRASÍLIA - UNICEUB
Faculdade de Ciências Exatas e Tecnologia FATECS
Curso de Bacharelado em Ciência da Computação
Disciplina: TEORIA DA COMPUTAÇÃO
Professor:Luis Alberto Martins Palhares de Melo
TRABALHO DE RECUPERAÇÃO – Menção máxima = MM
Nome Completo
Rubrica
INSTRUÇÕES
1) ATENÇÃO !!! Entregar o trabalho com a resolução das questões
totalmente escrita à mão !!! Não será aceita em hipótese alguma a entrega
da resolução das questões de qualquer parte do trabalho em meio
impresso !!! Os enunciados das questões deverão constar no documento
entregue e podem estar impressos.
2) O trabalho deve ser entregue impreterivelmente até 2a feira 16/06/2014 no
horário de aula, quando o aluno assinará o documento de registro de
entrega de seu trabalho ao professor
3) A menção máxima possível de ser obtida neste trabalho é MM
CENTRO UNIVERSITÁRIO DE BRASÍLIA - UNICEUB
Faculdade de Ciências Exatas e Tecnologia FATECS
Curso de Bacharelado em Ciência da Computação
Disciplina: TEORIA DA COMPUTAÇÃO
Professor:Luis Alberto Martins Palhares de Melo
Questão 1
É apresentado abaixo um AFN M = (Σ, Q, δ, q0, F)
Σ = { a, b, c } Q = { q0, q1, q2, q3 } F = { q1 ,q3 }
1 a) Justifique porquê o autômato é classificado como “não-determinístico”
1 b) Mostre a “sequência de processamento” que o AFN executa para a sentença w = “bcacba”. O
AFN aceita a sentença w ?
CENTRO UNIVERSITÁRIO DE BRASÍLIA - UNICEUB
Faculdade de Ciências Exatas e Tecnologia FATECS
Curso de Bacharelado em Ciência da Computação
Disciplina: TEORIA DA COMPUTAÇÃO
Professor:Luis Alberto Martins Palhares de Melo
Questão 2
Considere a gramática abaixo que gera sentenças da linguagem L onde
L = { w | w = 0m1, m ≥ 1 }.
A gramática acima gera sentenças que tenham os N primeiros bits 0 e o último bit é sempre 1.
2 A) Adapte a gramática para que, além das sentenças propostas que já gera, gere também todas as
sentenças com ao menos uma subpalavra “11”.
Obs. 1: Apenas para ilustrar, note que tal gramática deve gerar, após a adaptação da gramática, entre as
infinitas sentenças da linguagem L, por exemplo, as seguintes sentenças:
11011, 0000011,
011011011, 000001, 111, 100111001, 000111, 01, 000111000, 1010011, 011, etc.
CENTRO UNIVERSITÁRIO DE BRASÍLIA - UNICEUB
Faculdade de Ciências Exatas e Tecnologia FATECS
Curso de Bacharelado em Ciência da Computação
Disciplina: TEORIA DA COMPUTAÇÃO
Professor:Luis Alberto Martins Palhares de Melo
Questão 3
Considere o AFD definido sobre o alfabeto Σ={a,b}, que reconhece sentenças de determinada
linguagem L, conforme apresentado abaixo e faça o que se pede :
Questão 3.1) Este AFD reconhece um número finito ou infinito de sentenças ?
Questão 3.2) Quais são os estados não finais deste AFD ?
Questão 3.3) Quais são os estados finais deste AFD ?
Questão 3.4) Qual o estado do AFD após processar a sentença w = abbbb ?
A sentença w ∈ L ?
Questão 3.5) Qual o estado do AFD após processar a sentença w = abbbbaaaaab ?
A sentença w ∈ L ?
Questão 3.6) Qual o estado do AFD após processar a sentença w = abbbbaaaaa ?
A sentença w ∈ L ?
Questão 3.7) Qual o estado do AFD após processar a sentença w = abbbbaba ?
A sentença w ∈ L ?
Questão 3.8) Qual o estado do AFD após processar a sentença w = babbbbaba ?
A sentença w ∈ L ?
Questão 3.9) A linguagem L, que está formalmente definida pelo AFD apresenta um número finito ou
infinito de sentenças ?
CENTRO UNIVERSITÁRIO DE BRASÍLIA - UNICEUB
Faculdade de Ciências Exatas e Tecnologia FATECS
Curso de Bacharelado em Ciência da Computação
Disciplina: TEORIA DA COMPUTAÇÃO
Professor:Luis Alberto Martins Palhares de Melo
Questão 4
Construa uma gramática regular G sobre o alfabeto Σ={0,1} que gera SENTENÇAS da linguagem L
onde as sentenças não possuem a subpalavra “101”
Questão 5
Construa a gramática regular G sobre o alfabeto Σ={0,1} que gera SENTENÇAS da linguagem L onde
as sentenças tenham, obrigatoriamente, “00” ou “11”como subpalavras
Questão 6
Construa um AFD sobre o alfabeto Σ={0,1} que reconheça SENTENÇAS da linguagem L onde as
sentenças possuem ou um número par de bits “1” e um número ímpar de bits “0”, ou um número ímpar
de bits “1” e um número par de bits “0”
Questão 7
Construa um AFD sobre o alfabeto Σ={0,1} que reconheça SENTENÇAS da linguagem L onde as
sentenças possuem no máximo um par da subpalavra “00”
Questão 8
Escreva um autômato de pilha (AP) para reconhecer sentenças w da linguagem L sobre o alfabeto Σ =
{b, o, m, d, i, a, s, e, u, j } tal que
L = { w | w = (bom)x (dia)x+1 (seu)k-1(jose)k onde x ≥ 0, k ≥ 1 }
CENTRO UNIVERSITÁRIO DE BRASÍLIA - UNICEUB
Faculdade de Ciências Exatas e Tecnologia FATECS
Curso de Bacharelado em Ciência da Computação
Disciplina: TEORIA DA COMPUTAÇÃO
Professor:Luis Alberto Martins Palhares de Melo
Questão 9
Escreva um autômato de pilha (AP) para reconhecer sentenças w da linguagem L sobre o alfabeto Σ =
{b, o, m, d, i, a, s, e, u, j } tal que
L = { w | w = (bom)x (dia)k+1 (seu)k-1(jose)x-2 onde x ≥ 2, k ≥ 1 }
Questão 10
Projete uma Máquina de Turing sobre o alfabeto Σ = {a,b,c} que reconheça sentenças w da linguagem
L onde
L = { w | w = anbncn onde n ≥ 1 }