Baixe o app para aproveitar ainda mais
Prévia do material em texto
UNIVERSIDADE ESTADUAL DE MARINGÁ – UEM CENTRO DE TECNOLOGIA – CTC DEPARTAMENTO DE INFORMÁTICA – DIN BACHARELADO EM CIÊNCIA DA COMPUTAÇÃO DISCIPLINA: TEORIA DA COMPUTAÇÃO PROFESSOR: YANDRE MALDONADO E GOMES DA COSTA Lista de Exercícios no 2 – Autômato Finito Determinístico (AFD) 1. Descreva a definição de AFD. Um AFD é uma quíntupla <Σ, S, S0, δ, F>, onde: � Σ é o alfabeto de entrada; � S é um conjunto finito não vazio de estados; � S0 é o estado inicial, S0 ∈ S ; � δ é a função de transição de estados, definida δ: S x Σ → S ; � F é o conjunto de estados finais, F⊆ S . 2. Dado o alfabeto ∑ = {a,b}, construa AFDs para as seguintes linguagens: a) {b(ab)nb | n≥0} b) { banba | n≥0} S0 S1 b S3 b S2 a b S0 S1 b S2 b a S3 a c) {ambn | m+n é par} d) {abmba(ab)n | m, n ≥0} 3. Seja ∑ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, construa AFDs para as seguintes linguagens: a) {x ∈∑+ | a seqüência descrita por x corresponda a um valor inteiro par} b) {x ∈∑+ | a seqüência descrita por x corresponda a um valor inteiro divisível por 5} S0 S1 a S2 b S3 b b a b S0 S1 a S2 b S4 a b S3 a b S0 S1 0, 2, 4, 6, 8 0, 2, 4, 6, 8 1, 3, 5, 7, 9 1, 3, 5, 7, 9 S0 S1 0, 5 0, 5 1, 2, 3, 4, 6, 7, 8, 9 1, 2, 3, 4, 6, 7, 8, 9 c) {x ∈∑+ | a seqüência descrita por x corresponda a um valor inteiro ímpar} 4. Descreva um algoritmo de um AFD. Início Estado Atual ← Estado Inicial; Para I variar do Símbolo inicial da fita até o símbolo final Faça Se Existe δ (Estado Atual, I) Então Estado Atual ← δ (Estado Atual, I); Senão REJEITA; Se Estado Atual é estado final Então ACEITA; Senão REJEITA; Fim. 5. Qual é a linguagem definida pelo seguinte autômato? L = { w ∈ {a, b}* | |w|a = 2n+1 ∧ |w|b = 2m+1 ∧ n, m≥0 } ou L = { w ∈ {a, b}* | a quantidade de símbolos ‘a’ e a quantidade de símbolos ‘b’ em w é ímpar} S0 S2 Sf S1 b b b b a a a a S0 S1 1, 3, 5, 7, 9 1, 3, 5, 7, 9 0, 2, 4, 6, 8 0, 2, 4, 6, 8
Compartilhar