primeiraLista2020

Prévia do material em texto

Universidade Federal do Amazonas
Departamento de Ciência da Computação
Fundamentos Teóricos da Computação - 2021/2
Prof. Dr. Ruiter Braga Caldas
1ª Lista de Exercícios
 1. Construa AFDs para reconhecer as seguintes linguagens:
 a) {w ∈ {0,1} | toda posição impar de w tem o caractere “1”}.
 b) {w ∈ {0,1} | w tem número par de 0's (consecutivos ou não) e dois 1's}
 c) {w ∈ {0,1,2,3} | w é múltiplo de 3 & múltiplo de 4}
 d) {w ∈ {0,1} | w tem número par de 10's ou ímpar de 0's}
 e) {w ∈ {0,1} | w de tamanho ímpar terminadas em 1}.
 f) {w ∈ {0,1} | w = 0n0n}, se não conseguir resolver descreva a dificuldade encontrada.
 2. Construa AFDs para reconhecer as linguagens solicitadas, todo os alfabetos são Σ={a,b}:
 a) {w | w tem pelo menos dois “a” e mais de dois “b”}.
 b) {w | w tem exatamente três “a” e pelo menos dois “b”}.
 c) {w | w tem um número par de “a” e termina com “b”}.
 d) {w | w tem tamanho par e um número ímpar de “b”}.
 e) {w | w possui a sub-cadeia “bb” pelo menos duas vezes }.
 f) {w | w tem pelo menos dois “b” e no mínimo dois “a”}.
 3. Construa um AFD, com alfabeto={0,1}, que aceitam as linguagens: 
 a) {Toda sub-cadeia 00 deve ser seguida imediatamente por um 1}. 
 obs. As cadeias 101, 0010, 0010011001 são aceitas. Mas as cadeias 0001, 00100 não são
aceitas.
 b) {Toda as cadeia contêm 00 mas não devem conter 000}.
 c) {O símbolo mais a esquerda é diferente do símbolo mais a direita}.
 d) {Toda sub-cadeia de tamanho 4 deve ter no máximo dois “0”}. 
 obs. As cadeias 001110, 011001 são aceitas. Mas as cadeias 10010 não é aceita.
 4. Construa AFNs para reconhecer as seguintes linguagens:
 a) {w ∈ {a,b} | w contém a substring “aa” ou substring “bb”}.
 b) {w ∈ {a,b} | w contém ambas as substring “aa” e “bb” ou nenhuma delas}.
 c) {w ∈ {a,b} | onde todo “a” é seguido por “b” ou “ab”}.
 d) {w ∈ {a,b,c} | w tem tamanho 3 e cada caractere aparece uma única vez}.
 e) {w ∈ {a,b} | onde o terceiro caractere do início é “b” e o terceiro antes do final é “b”}.
 5. Construa o AFN M1 que reconhecer a linguagens (ba)* e AFN M2 que reconhecer a 
linguagens (ab)+, em seguida use a transição lambda para construir o AFN M que reconhece 
a linguagens (ba)* (ab)+. Gere o AFD equivalente.
 6. Sejam os seguintes autômato finito não-determinístico a seguir, para cada um deles faça o 
que se pede:
 a) Calcule o fecho lambda de cada estado (fecho Épsilon)
 b) Mostre a tabela da função de transição de estados δ para o AFN.
Universidade Federal do Amazonas
Departamento de Ciência da Computação
Fundamentos Teóricos da Computação - 2021/2
Prof. Dr. Ruiter Braga Caldas
 c) Use o algoritmo descrito em sala para gerar o AFD equivalente. 
 d) Descreva a linguagem aceita pelo AFD.
a) b)
 7. Converta as seguintes expressões regulares em AFNs.
 a) a(abb)*  b
 b) a+  (ab)+ 
 c) (a  b+ ) a+ b+ 
 d) a(ba) * b
 e) (  a) b
 8. Converta os AFNs em expressões regulares.
 a)
Universidade Federal do Amazonas
Departamento de Ciência da Computação
Fundamentos Teóricos da Computação - 2021/2
Prof. Dr. Ruiter Braga Caldas
 b)
 c)
Observações: 
1. As respostas devem ser entregue implementados na ferramenta Jflap. 
2. Os arquivos devem ser zipados e enviados por email até o dia da Primeira Avaliação. 
3. O nome dos arquivos de cada questão devem seguir o seguinte padrão em Maiúscula: 
 
 “nome_aluno”-L01Q01A.jff , 
 
 onde L1 - Primeira Lista, 
 Q1A - Questão 01 letra A.