Conversión de autómata finito con transiciones-ε y no determinista a autómata finito...

C ompiladoresE l comi enzo …

Conversión de autómata finito con transiciones-ε y no determinista a autómata finito determinista

Estados

Entradas

a b c

q0 q1 q2 q3 q4a b

b

b,

c a

C ompiladoresE l comi enzo …

Estados

Entradas

a b c

q0 q1 q2 q3 q4a b

b

b,

c a

C ompiladoresE l comi enzo …

Estados

Entradas

a b c

qA{ q0,q3 }

q0 q1 q2 q3 q4a b

b

b,

c a

C ompiladoresE l comi enzo …

Estados

Entradas

aa b c

qA{ q0,q3 } qB{ q1,q4,q2 }

qB{ q1,q4,q2 }

q0 q1 q2 q3 q4a b

b

b,

c a

C ompiladoresE l comi enzo …

Estados

Entradas

aa b c

qA{ q0,q3 } qB{ q1,q4,q2 } qC{ q3 }

qC{ q3 }

q0 q1 q2 q3 q4a b

b

b,

c a

qB{ q1,q4,q2 }

C ompiladoresE l comi enzo …

Estados

Entradas

aaa b c

qA{ q0,q3 } qB{ q1,q4,q2 } qC{ q3 }

qC{ q3 }

q0 q1 q2 q3 q4a b

b

b,

c a

qB{ q1,q4,q2 }

C ompiladoresE l comi enzo …

Estados

Entradas

qA{ q0,q3 } qB{ q1,q4,q2 } qC{ q3 }

qC{ q3 }

aaa b c

q0 q1 q2 q3 q4a b

b

b,

c a

qB{ q1,q4,q2 }

C ompiladoresE l comi enzo …

Estados

Entradas

qA{ q0,q3 } qB{ q1,q4,q2 } qC{ q3 }

qC{ q3 }

aaa b c

qD{ q1,q2 }

qD{ q1,q2 }

q0 q1 q2 q3 q4a b

b

b,

c a

qB{ q1,q4,q2 }

C ompiladoresE l comi enzo …

Estados

Entradas

qA{ q0,q3 } qB{ q1,q4,q2 } qC{ q3 }

qC{ q3 }

aaa b c

qD{ q1,q2 } qC{ q3 }

qD{ q1,q2 }

q0 q1 q2 q3 q4a b

b

b,

c a

qB{ q1,q4,q2 }

C ompiladoresE l comi enzo …

Entradas

qE{ q4,q2 }

Estados

qA{ q0,q3 } qB{ q1,q4,q2 } qC{ q3 }

qC{ q3 }

aaa b c

qD{ q1,q2 } qC{ q3 }

qD{ q1,q2 }

qE{ q4,q2 }

q0 q1 q2 q3 q4a b

b

b,

c a

qB{ q1,q4,q2 }

C ompiladoresE l comi enzo …

Entradas

qE{ q4,q2 }

Estados

qA{ q0,q3 } qB{ q1,q4,q2 } qC{ q3 }

qC{ q3 }

aaa b c

qD{ q1,q2 } qC{ q3 }

qD{ q1,q2 }

qE{ q4,q2 }

qD{ q1,q2 } qC{ q3 }

q0 q1 q2 q3 q4a b

b

b,

c a

qB{ q1,q4,q2 }

C ompiladoresE l comi enzo …

Entradas

qE{ q4,q2 }

Estados

qA{ q0,q3 } qB{ q1,q4,q2 } qC{ q3 }

qC{ q3 }

aaa b c

qD{ q1,q2 } qC{ q3 }

qD{ q1,q2 }

qE{ q4,q2 }

qD{ q1,q2 }

qC{ q3 }

qC{ q3 }

q0 q1 q2 q3 q4a b

b

b,

c a

qB{ q1,q4,q2 }

C ompiladoresE l comi enzo …

Entradas

Estados

qA{ q0,q3 }

qC{ q3 }

aaa b c

qD{ q1,q2 }

qE{ q4,q2 }

q0 q1 q2 q3 q4a b

b

b,

c a

qE{ q4,q2 }

qB{ q1,q4,q2 } qC{ q3 }

qD{ q1,q2 } qC{ q3 }

qD{ q1,q2 }

qC{ q3 }

qC{ q3 }

qB{ q1,q4,q2 }

C ompiladoresE l comi enzo …

Entradas

Estados

qA{ q0,q3 }

qC{ q3 }

aaa b c

qD{ q1,q2 }

qE{ q4,q2 }

q0 q1 q2 q3 q4a b

b

b,

c a

qA

qE{ q4,q2 }

qB{ q1,q4,q2 } qC{ q3 }

qD{ q1,q2 } qC{ q3 }

qD{ q1,q2 }

qC{ q3 }

qC{ q3 }

qC

qB

qE

qD

a

b

C C

a

C

b

b

qB{ q1,q4,q2 }

C ompiladoresE l comi enzo …

Entradas

Estados

qA{ q0,q3 }

qC{ q3 }

aaa b c

qD{ q1,q2 }

qE{ q4,q2 }

q0 q1 q2 q3 q4a b

b

b,

c a

qE{ q4,q2 }

qB{ q1,q4,q2 } qC{ q3 }

qD{ q1,q2 } qC{ q3 }

qD{ q1,q2 }

qC{ q3 }

qC{ q3 }

qA

qC

qB

qE

qD

a

b

C C

a

C

b

b

qB{ q1,q4,q2 }

C ompiladoresE l comi enzo …

Entradas

Estados

qA{ q0,q3 }

qC{ q3 }

aaa b c

qD{ q1,q2 }

qE{ q4,q2 }

q0 q1 q2 q3 q4a b

b

b,

c a

qE{ q4,q2 }

qB{ q1,q4,q2 } qC{ q3 }

qD{ q1,q2 } qC{ q3 }

qD{ q1,q2 }

qC{ q3 }

qC{ q3 }

qA

qC

qB

qE

qD

a

b

C C

a

b

b

C

qB{ q1,q4,q2 }

C ompiladoresE l comi enzo …

Entradas

Estados

qA{ q0,q3 }

qC{ q3 }

aaa b c

qD{ q1,q2 }

qE{ q4,q2 }

q0 q1 q2 q3 q4a b

b

b,

c a

qE{ q4,q2 }

qB{ q1,q4,q2 } qC{ q3 }

qD{ q1,q2 } qC{ q3 }

qD{ q1,q2 }

qC{ q3 }

qC{ q3 }

qA

qC

qB

qE

qD

a

b

C C

a

b

b

C

qB{ q1,q4,q2 }

C ompiladoresE l comi enzo …

Entradas

Estados

qA{ q0,q3 }

qC{ q3 }

aaa b c

qD{ q1,q2 }

qE{ q4,q2 }

q0 q1 q2 q3 q4a b

b

b,

c a

qE{ q4,q2 }

qB{ q1,q4,q2 } qC{ q3 }

qD{ q1,q2 } qC{ q3 }

qD{ q1,q2 }

qC{ q3 }

qC{ q3 }

qA

qC

qB

qE

qD

a

b

C C

a

b

b

C

qB{ q1,q4,q2 }

C ompiladoresE l comi enzo …

Entradas

Estados

qA{ q0,q3 }

qC{ q3 }

aaa b c

qD{ q1,q2 }

qE{ q4,q2 }

q0 q1 q2 q3 q4a b

b

b,

c a

qE{ q4,q2 }

qB{ q1,q4,q2 } qC{ q3 }

qD{ q1,q2 } qC{ q3 }

qD{ q1,q2 }

qC{ q3 }

qC{ q3 }

qA

qC

qB

qE

qD

a

b

C C

a

b

b

C

qB{ q1,q4,q2 }