Construcción de Thompson
Construiremos el NFA, M?(?1??2, Q1?Q2?{q0, qf}, q0, {qf}, ?)
donde q0 es un nuevo estado inicial y qf un estado final y ? se define:
- ?(q0, ?) = {q1, q2}
- ?(q, a) = ?1(q, a) ? q ? Q1-{f1} y a ? ?1?{?}
- ?(q, a) = ?2(q, a) ? q ? Q2-{f2} y a ? ?2?{?}
- ?(f1, ?) = ?(f2, ?) = {qf}