Computer Engineering

CENTRO UNIVERSITÁRIO DE ANÁPOLIS
UNIEVANGÉLICA
CURSOS SUPERIORES DE COMPUTAÇÃO

Exercícios
1. Escreva AFD´s que aceitam as seguintes linguagens:
∑ = {0,1}
a) L={w|w possui nenhum ou vários 0´s como prefixo e um ou vários 0´s como sufixo} b) L={w|w possui 00 ou 111 como prefixo}
c) L={w|w possui quantidade ímpar de 0´s ou de 1´s}
d) L={w|w possui quantidade par de 0´s e de 1´s}
e) L={w|w não possui 00 como subpalavra}
∑ = {a,b,c}
f) L={w|w são todas as cadeias com abb como subpalavra}.
g) L={w|w são todas as cadeias que possuem exatamente 3 símbolos a}.
h) L={w|w são todas as cadeias que começam e terminam com a e que contenham pelo menos um b}.
2.
a)
b)
c)
d)
e)
f)
g)
h)
i)
j)
k)
l)

Construa os seguintes autômatos finitos determinísticos.
{w {0,1}* | w tem tamanho 3}
{w {0,1}* | w tem tamanho menor que 3}
{w {0,1}* | w tem tamanho maior que 3}
{w {0,1}* | w tem tamanho múltiplo de 3}
{w {0,1}* | cada 0 de w é imediatamente seguido de, no mínimo dois 1´s}
{w {0,1}* | os primeiros 4 símbolos de w contêm, no mínimo, dois 1´s}
{w {0,1}* | w NÃO contém 000 nem 111}
{w {0,1}* | os últimos três símbolos de w NÃO são 000}
{w {0,1,2}* | w tem número par de 0´s, par de 1´s e par de 2´s}
{w {a,b}* | w começa com a e tem tamanho par}
{w {a,b}* | w nunca tem mais de dois a´s consecutivos}
{w {a,b}* | w tem um número ímpar de ab´s}