Automatas finitos

INFORMATICA TEÓRICA Curso 2008-2009

Prácticas Tema 4 AUTÓMATAS FINITOS

Práctica 4.1: Construcción de autómatas finitos.
1.- Construir autómatas finitos deterministas que reconozcan lossiguientes lenguajes: L1= { am bn⏐ m > 0, n > 0 } L2 = { x ∈ {0,1}* ⏐ en x aparece el 1 dos o tres veces, la primera y la segunda de las cuales no son consecutivas } L3 = { x ∈ {a,b}* ⏐ Na(x) es par } L4 = {x ∈ {a,b}* ⏐ x acaba en a } 2.- Construir un AFD mínimo que reconozca las palabras sobre el alfabeto Σ = {a,b,c,d} que contienen un número par (eventualmente cero) de apariciones de la subcadena bcd.3.- Sea el alfabeto Σ = {0,1}. Encontrar el AFD que reconoce el lenguaje: L = { Σ*- {λ} ⏐ la subcadena 101 no aparezca } 4.- Construir un AFD mínimo que reconozca el conjunto de los números positivosmúltiplos de 3: a) 003 y 000 son válidas. b) No son palabras del lenguaje las que tienen ceros no significativos a la izquierda. 5.- Construir un autómata finito que reconozca el siguiente lenguaje:L = { x ∈ {a,b}* ⏐ Na(x) = 3 y Nb(x) = 4 + 2}

Práctica 4.2: Minimización de AF.
1.- Dados los AF definidos por los siguientes diagramas de transición:
Ap
0

p1
1 0 0 1

p3

p5
0 0 01 1

p7

1

p2
0,1

1

p4

0

p6

1

p8

Aq
1 1

q1
0 0

q3

1

q5
0

1 1

q7

1

1 0

1

q2
0

0

q4
0 0

q6

q8

At

1 1 0 1 1 1 0 1

t11

t4

t6

t7

0

t2

0

t3
0

0

t5
0

Ar
0 0 1 1 1 0 0 0

r

s

t

x

0

1

u
0,1

1

w

1

y

Obtener para cada uno de ellos el autómata mínimo.Establecer si son o no equivalentes: - por suma directa de autómatas. - cuáles son isomorfos.

Práctica 4.3: Isomorfismo de AF.
1.- a) Dado el afd A, obtener el autómata finito mínimo equivalenteÂ.

A
0

q0

1 1 q2 1 0 q3 1

1 q4

0

0 q5

1

1

q1 0

0

0

q6

b) Dado el autómata A’, probar que es equivalente a Â, utilizando el autómata suma.
1 0 0 q’1 0

A’
1...