Diseño de Afn's

Diseño de Autómatas Finitos No Deterministas (AFND)
1. Diseñar, mediante unión, un AFND que acepte el lenguaje de las palabras en {0,1}* que si no contienen la subcadena“000”, contienen la subcadena “111”. No olvides eliminar la implicación antes de describir los lenguajes.

Descripción de lenguajes a unir
L1
Palabras que no contienen “000”
L2Palabras que contienen “111”
0.
Descripción de Estados:
Leng
Edo
Condición que recuerda
L1
Q0
Palabra vacia
L2
Q1
Palabras con 0 o con 1
L3
Q2
Palabras con 0 ocon 1 y “111”
L4
Q3
Palabras con 0 o con 1
L5
Q4
Palabras con 0 o con 1 y “000”




AFND:











2. Diseñar, mediante concatenación, un AFND queacepte el lenguaje de las palabras en {a,b}* que inician con un número par de a’s, terminan con un número impar de a’s y contienen al menos una b.

Descripción de lenguajes aconcatenar
L1 (inicio)
Palabras que contienen un numero par de “a” ’s
L2 (en medio)
Palabra que contiene al menos una “b”
L3 (final)
Palabras que contienen un numeroimpar de “a” ’s
0.
Descripción de Estados:
Leng
Edo
Condición que recuerda
L1
q0
Palabras que contienen un numero par de “a”
L1
q0
Palabras que contienen un numeroimpar de “a”
L2
q2
Palabras que solamente contienen un numero par de “a”
L2
q3
Palabras que empiezan con numero par de “a” y tienen al menos una b
L2
q4
Palabrasque empiezan con numero par de “a” , tienen al menos una b y no terminan en b
L3
q5
Palabras que empiezan con numero par de “a” , tienen al menos una b y termina en numeropar de “a”
L3
q6
Palabras que empiezan con numero par de “a” , tienen al menos una b y termina en numero impar de “a”










AFND: