Automata Language

Kelompok 14 AZHARI HARAHAP EVA NATALIS SINUHAJI CUNDA DWI SESPADANA RAHIM RASYID FACHRAN NAZARULLAH

G64086057 G64086058 G64086059 G64086060 G64086061

1. Bahasa regular menjadi DFA a. ( 11 + 10 )*

Tabel Transisi Tabel eclose δ 0 1 Ɛ q eclose(q) Ø Ø {B,I} A {A,B,I} A B Ø {C} Ø B {B} C Ø Ø {D,E} C {C,D,E} D Ø {F} Ø D {D} E {G} Ø Ø E {E} F Ø Ø {H} F {B,F,H,I} G Ø Ø {H} G {B,G,H,I} H Ø Ø {B,I} H {H,B,I} *I Ø Ø Ø I { I} Start statem qD = eclose(A) = {A,B,I} Fungsi transisi dimulai dari state {A,B,I} a. state {A,B,I} • δD ({A,B,I},0) = U eclose(rj); rj ϵ U δ(pi,0); pi ϵ {A,B,I} rj = δ(A,0) U δ(B,0) U δ(I,0) = Ø U Ø U Ø = Ø δD ({A,B,I},0) = U eclose(Ø) = Ø • δD ({A,B,I},1) = U eclose(rj); rj ϵ U δ(pi,1); pi ϵ {A,B,I} rj = δ(A,1) U δ(B,1) U δ(I,1) = Ø U {C} U Ø = {C} δD ({A,B,I},1) = U eclose(C) = {C,D,E} b. state {C,D,E} • δD ({C,D,E},0) = U eclose(rj); rj ϵ U δ(pi,0); pi ϵ { C,D,E} rj = δ(C,0) U δ(D,0) U δ(E,0) = Ø U Ø U {G} = {G} δD ({C,D,E},0) = U eclose(G) = {B,G,H,I} • δD ({C,D,E},1) = U eclose(rj); rj ϵ U δ(pi,1); pi ϵ { C,D,E } rj = δ(C,1) U δ(D,1) U δ(E,1) = Ø U {F} U Ø = {F} δD ({C,D,E},1) = U eclose(F) = {B,F,H,I} c. state {B,G,H,I} • δD ({B,G,H,I },0) = U eclose(rj); rj ϵ U δ(pi,0); pi ϵ { B,G,H,I } rj = δ(B,0) U δ(G,0) U δ(H,0) U δ(I,0) = Ø U Ø U Ø U Ø = Ø δD ({B,G,H,I },0) = U eclose(Ø) = Ø

•

δD ({B,G,H,I },1) = U eclose(rj); rj ϵ U δ(pi,1); pi ϵ { B,G,H,I } rj = δ(B,1) U δ(G,1) U δ(H,1) U δ(I,1) = {C} U Ø U Ø U Ø = {C} δD ({B,G,H,I },1) = U eclose(F) = { C,D,E } d. state {B,F,H,I} • δD ({B,F,H,I },0) = U eclose(rj); rj ϵ U δ(pi,0); pi ϵ { B,F,H,I } rj = δ(B,0) U δ(F,0) U δ(H,0) U δ(I,0) = Ø U Ø U Ø U Ø = Ø δD ({B,F,H,I },0) = U eclose(Ø) = Ø • δD ({B,F,H,I },1) = U eclose(rj); rj ϵ U δ(pi,1); pi ϵ { B,F,H,I } rj = δ(B,1) U δ(F,1) U δ(H,1) U δ(I,1) = {C} U Ø U Ø U Ø = {C} δD ({B,F,H,I },1) = U eclose(F) = { C,D,E }

b.

( 111 + 100 )* 0

Tabel Transisi δ 0 Ø A B Ø C Ø D Ø E {G} F Ø G Ø H Ø I {K} J Ø K Ø L Ø

1 Ø {C} Ø {F} Ø Ø Ø {J} Ø Ø Ø Ø

Ɛ {B,M} Ø {D,E} Ø Ø { H} {I} Ø Ø {L} {L} {B, M}

Tabel eclose q eclose(q) A {A,B,M} B {B} C {C,D,E} D {D} E {E} F { F,H } G { G,I} H {H } I { I} J {B,J,L,M} K {B,K,L,M} L {B,L,M}

M {N} Ø Ø M {M} *N Ø Ø Ø N {N} Start statem qD = eclose(A) = {A,B,M} Fungsi transisi dimulai dari state {A,B,M} a. state {A,B,M} • δD ({A,B,M},0) = U eclose(rj); rj ϵ U δ(pi,0); pi ϵ {A,B,M} rj = δ(A,0) U δ(B,0) U δ(M,0) = Ø U Ø U {N} = {N} δD ({A,B,M},0) = U eclose(N) = {N} • δD ({A,B,M},1) = U eclose(rj); rj ϵ U δ(pi,1); pi ϵ {A,B,I} rj = δ(A,1) U δ(B,1) U δ(M,1) = Ø U {C} U Ø = {C} δD ({A,B,M},1) = U eclose(C) = {C,D,E} b. state {C,D,E} • δD ({C,D,E},0) = U eclose(rj); rj ϵ U δ(pi,0); pi ϵ { C,D,E} rj = δ(C,0) U δ(D,0) U δ(E,0) = Ø U Ø U {G} = {G} δD ({C,D,E},0) = U eclose(G) = {G,I} • δD ({C,D,E},1) = U eclose(rj); rj ϵ U δ(pi,1); pi ϵ { C,D,E } rj = δ(C,1) U δ(D,1) U δ(E,1) = Ø U {F} U Ø = {F} δD ({C,D,E},1) = U eclose(F) = {F,H} c. state {N} • δD ({N},0) = U eclose(rj); rj ϵ U δ(pi,0); pi ϵ { N} rj = δ(N,0) = Ø δD ({N},0) = U eclose(Ø) = Ø • δD ({N},1) = U eclose(rj); rj ϵ U δ(pi,1); pi ϵ { N } rj = δ(N,1) = Ø δD ({N},1) = U eclose(Ø) = Ø d. state {G,I} • δD ({G,I },0) = U eclose(rj); rj ϵ U δ(pi,0); pi ϵ { G, I } rj = δ(G,0) U δ(I,0) = Ø U {K} = {K} δD ({G, I },0) = U eclose(K) = {B,K,L,M} • δD ({G, I },1) = U eclose(rj); rj ϵ U δ(pi,1); pi ϵ { G,I } rj = δ(G,1) U δ(I,1) = Ø U Ø = Ø δD ({G, I },1) = U eclose(Ø) = Ø e. state { F,H} • δD ({F,H },0) = U eclose(rj); rj ϵ U δ(pi,0); pi ϵ { F,H } rj = δ(F,0) U δ(H,0) = Ø U Ø = Ø δD ({F,H },0) = U eclose(Ø) = Ø • δD ({F,H},1) = U eclose(rj); rj ϵ U δ(pi,1); pi ϵ {F,H} rj = δ(F,1) U δ(H,1) = Ø U {J} = {J} δD ({F,H },1) = U eclose(J) = { B,J,L,M } f. state { B,K,L,M} • δD ({B,K,L,M },0) = U eclose(rj); rj ϵ U δ(pi,0); pi ϵ { B,K,L,M } rj = δ(B,0) U δ(K,0) U δ(L,0) U δ(M,0) = Ø U Ø U Ø U {N} = {N} δD ({B,K,L,M },0) = U eclose(N) = {N} • δD ({B,K,L,M },1) = U eclose(rj); rj ϵ U δ(pi,1); pi ϵ { B,K,L,M } rj = δ(B,1) U δ(K,1) U δ(L,1) U δ(M,1) = {C} U Ø U Ø U Ø = {C} δD ({B,K,L,M },1) = U eclose(C) = { C,D,E } g. state { B,J,L,M } • δD ({B,J,L,M },0) = U eclose(rj); rj ϵ U δ(pi,0); pi ϵ { B,J,L,M } rj = δ(B,0) U δ(J,0) U δ(L,0) U δ(M,0) = Ø U Ø U Ø U {N} = {N} δD ({B,J,L,M },0) = U eclose(N) = {N}

•

c.

δD ({B,J,L,M },1) = U eclose(rj); rj ϵ U δ(pi,1); pi ϵ { B,J,L,M } rj = δ(B,1) U δ(J,1) U δ(L,1) U δ(M,1) = {C} U Ø U Ø U Ø = {C} δD ({B,J,L,M },1) = U eclose(J) = { C,D,E }

0 + 10* + 01*0

Tabel Transisi δ 0 Ø A B Ø C {D} D Ø E Ø F Ø G Ø H Ø I {J} J Ø K Ø

1 Ø Ø Ø Ø Ø {G} Ø Ø Ø Ø Ø

Ɛ {B,L} {C,F} Ø {E} {T} Ø {H} {I,K} Ø {I} {E}

Tabel eclose q A B C D E F G H I J K

eclose(q) {A,B,C,F,L} {B,C,F} {C} {D,E,T} {E,T} { F,} {G,H,I,K,E,T} {H,I,K,E,T} { I} { I,J,K,E,T} {K,E,T}

L {M} Ø Ø L {L} M Ø Ø {N} M {M} N Ø Ø {O,Q} N {M,N,O,Q,R} O Ø {P} Ø O {O} P Ø Ø {Q} P {O,P,Q,R} Q Ø Ø {R} Q {Q,R} R {S} Ø Ø R {R} S Ø Ø {T} S {S,T} *T Ø Ø Ø T {T} Start statem qD = eclose(A) = {A,B,C,F,L} Fungsi transisi dimulai dari state { A,B,C,F,L } a. state { A,B,C,F,L } • δD ({A,B,C,F,L },0) = U eclose(rj); rj ϵ U δ(pi,0); pi ϵ {A,B,M} rj = δ(A,0) U δ(B,0) U δ(C,0) U δ(F,0) U δ(L,0) = Ø U Ø U {D}U Ø U {M} = {D,M} δD ({A,B,C,F,L },0) = U eclose(D,M) = { D,E,M,T } • δD ({A,B,C,F,L },1) = U eclose(rj); rj ϵ U δ(pi,1); pi ϵ {A,B,I} rj = δ(A,1) U δ(B,1) U δ(C,1) U δ(F,1) U δ(L,1) = Ø U Ø U Ø U {G} U Ø = {G} δD ({A,B,C,F,L },1) = U eclose(G) = { G,H,I,K,E,T } b. state {D,M,E,T} • δD ({D,M,E,T },0) = U eclose(rj); rj ϵ U δ(pi,0); pi ϵ { D,M,E,T } rj = δ(D,0) U δ(M,0) U δ(E,0) U δ(T,0) = Ø U Ø U Ø U Ø = Ø δD ({D,M,E,T },0) = U eclose(Ø) = Ø • δD ({D,M,E,T },1) = U eclose(rj); rj ϵ U δ(pi,1); pi ϵ { D,M,E,T } rj = δ(D,1) U δ(M,1) U δ(E,1) U δ(T,1) = Ø U Ø U Ø U Ø = Ø δD ({D,M,E,T },1) = U eclose(Ø) = Ø c. state { G,H,I,K,E,T } • δD ({G,H,I,K,E,T },0) = U eclose(rj); rj ϵ U δ(pi,0); pi ϵ {G,H,I,K,E,T } rj = δ(G,0) U δ(H,0) U δ(I,0) U δ(K,0) U δ(E,0) U δ(T,0) = Ø U Ø U {J} U Ø U Ø U Ø = {J} δD ({G,H,I,K,E,T },0) = U eclose(J) = { I,J,K,E,T} • δD ({G,H,I,K,E,T },1) = U eclose(rj); rj ϵ U δ(pi,1); pi ϵ { G,H,I,K,E,T} rj = δ(G,1) U δ(H,1) U δ(I,1) U δ(K,1) U δ(E,1) U δ(T,1) = Ø U Ø U Ø UØUØUØ=Ø=Ø δD ({G,H,I,K,E,T },1) = U eclose(Ø) = Ø d. state { I,J,K,E,T } • δD ({I,J,K,E,T },0) = U eclose(rj); rj ϵ U δ(pi,0); pi ϵ { I,J,K,E,T } rj = δ(I,0) U δ(J,0) U δ(K,0) U δ(E,0) U δ(T,0) = {J}U Ø U Ø U Ø U Ø U = {J} δD ({I,J,K,E,T },0) = U eclose(J) = { I,J,K,E,T } • δD ({I,J,K,E,T },1) = U eclose(rj); rj ϵ U δ(pi,1); pi ϵ { I,J,K,E,T } rj = δ(I,1) U δ(J,1) U δ(K,1) U δ(E,1) U δ(T,1) = Ø U Ø U Ø U Ø U Ø = Ø δD ({I,J,K,E,T },1) = U eclose(Ø) = Ø

2. NFA yang menerima string sedemikian sehingga pada bagian akhir string mengandung substring : 11, 22, 212, 2112, 21112, 33, 312123, 3111113, 3121113, dst.

3. DFA dari NFA yang ada di soal nomor 2 Table transisi q 1 2 q0 { q0, q1} { q0, q2} q1 { q4} Ø q2 { q2} { q4} q3 q3 q3 q4 Ø Ø Start state = q0 δA ({q0},1) = U δN (Pi, 1) = δN (q0, 1) = { q0, q1} δA ({q0},2) = U δN (Pi, 2) = δN (q0, 2) = { q0, q2} δA ({q0},3) = U δN (Pi, 3) = δN (q0, 3) = { q0, q3}

3 { q0, q3} Ø Ø q4 Ø

δA ({q0, q1},1) = U δN (Pi, 1) = δN (q0, 1) U δN (q1, 1) = { q0, q1,q4} δA ({q0, q1},2) = U δN (Pi, 2) = δN (q0, 2) U δN (q1, 2) = { q0, q2} δA ({q0, q1},3) = U δN (Pi, 3) = δN (q0, 3) U δN (q1, 3) = { q0, q3}

δA ({q0, q2},1) = U δN (Pi, 1) = δN (q0, 1) U δN (q2, 1) = { q0, q1,q2} δA ({q0, q2},2) = U δN (Pi, 2) = δN (q0, 2) U δN (q2, 2) = { q0, q2, q4} δA ({q0, q2},3) = U δN (Pi, 3) = δN (q0, 3) U δN (q2, 3) = { q0, q3} δA ({q0, q3},1) = U δN (Pi, 1) = δN (q0, 1) U δN (q3, 1) = { q0, q1,q3} δA ({q0, q3},2) = U δN (Pi, 2) = δN (q0, 2) U δN (q3, 2) = { q0, q2, q3} δA ({q0, q3},3) = U δN (Pi, 3) = δN (q0, 3) U δN (q3, 3) = { q0, q3, q4} δA ({q0, q1, q4},1) = U δN (Pi, 1) = δN (q0, 1) U δN (q1, 1) U δN (q4,1) ={q0, q1,q4} δA ({q0, q1, q4},2) = U δN (Pi, 2) = δN (q0, 1) U δN (q1, 1) U δN (q4,1) ={ q0, q2} δA ({q0, q1, q4},3) = U δN (Pi, 3) = δN (q0, 1) U δN (q1, 1) U δN (q4,1) = { q0, q3} δA ({q0, q1, q2},1) = U δN (Pi, 1) = δN (q0, 1) U δN (q1, 1) U δN (q2,1) = {q0, q1, q2,q4} δA ({q0, q1, q2},2) = U δN (Pi, 2) = δN (q0, 1) U δN (q1, 1) U δN (q2,1) ={ q0, q1,q4} δA ({q0, q1, q2},3) = U δN (Pi, 3) = δN (q0, 1) U δN (q1, 1) U δN (q2,1) = { q0, q3} δA ({q0, q2, q4},1) = U δN (Pi, 1) = δN (q0, 1) U δN (q2, 1) U δN (q4,1) = {q0,q1, q2} δA ({q0, q2, q4},2) = U δN (Pi, 2) = δN (q0, 1) U δN (q2, 1) U δN (q4,1) ={ q0, q2,q4} δA ({q0, q2, q4},3) = U δN (Pi, 3) = δN (q0, 1) U δN (q2, 1) U δN (q4,1) = { q0, q3} δA ({q0, q1, q3},1) = U δN (Pi, 1) = δN (q0, 1) U δN (q1, 1) U δN (q3,1) = {q0,q1, q3, q4} δA ({q0, q1, q3},2) = U δN (Pi, 2) = δN (q0, 1) U δN (q1, 1) U δN (q3,1) ={ q0, q2,q3} δA ({q0, q1, q3},3) = U δN (Pi, 3) = δN (q0, 1) U δN (q1, 1) U δN (q3,1) = { q0, q3, q4} δA ({q0, q2, q3},1) = U δN (Pi, 1) = δN (q0, 1) U δN (q2, 1) U δN (q3,1) = {q0,q1, q2, q3} δA ({q0, q2, q3},2) = U δN (Pi, 2) = δN (q0, 1) U δN (q2, 1) U δN (q3,1) ={ q0, q2,q3, q4} δA ({q0, q2, q3},3) = U δN (Pi, 3) = δN (q0, 1) U δN (q2, 1) U δN (q3,1) = { q0, q3, q4} δA ({q0, q3, q4},1) = U δN (Pi, 1) = δN (q0, 1) U δN (q3, 1) U δN (q4,1) ={q0,q1,q3} δA ({q0, q3, q4},2) = U δN (Pi, 2) = δN (q0, 1) U δN (q3, 1) U δN (q4,1) ={q0, q2,q3} δA ({q0, q3, q4},3) = U δN (Pi, 3) = δN (q0, 1) U δN (q3, 1) U δN (q4,1) ={q0,q3,q4} δA ({q0, q1, q2 , q4},1) = U δN (Pi, 1) = δN (q0, 1) U δN (q1, 1) U δN (q2,1) U δN (q4, 1) ={ q0, q1, q2,q4} δA ({q0, q1, q2 , q4},2) = U δN (Pi, 2) = δN (q0, 2) U δN (q1, 2) U δN (q2,2) U δN (q4, 2) ={ q0,q2,q4} δA ({q0, q1, q2 , q4},3) = U δN (Pi, 3) = δN (q0, 3) U δN (q1, 3) U δN (q2,3) U δN (q4, 3) ={q0,q3} δA ({q0, q1, q3 , q4},1) = U δN (Pi, 1) = δN (q0, 1) U δN (q1, 1) U δN (q3,1) U δN (q4, 1) ={ q0, q1, q3,q4} δA ({q0, q1, q3 , q4},2) = U δN (Pi, 2) = δN (q0, 2) U δN (q1, 2) U δN (q3,2) U δN (q4, 2) ={ q0,q2,q3} δA ({q0, q1, q3 , q4},3) = U δN (Pi, 3) = δN (q0, 3) U δN (q1, 3) U δN (q3,3) U δN (q4, 3) ={q0,q3,q4} δA ({q0, q1, q2 , q3},1) = U δN (Pi, 1) = δN (q0, 1) U δN (q1, 1) U δN (q2,1) U δN (q3, 1) ={ q0, q1, q2,q3,q4} δA ({q0, q1, q2 , q3},2) = U δN (Pi, 2) = δN (q0, 2) U δN (q1, 2) U δN (q2,2) U δN (q3, 2) ={ q0,q2, q3,q4} δA ({q0, q1, q2 , q3},3) = U δN (Pi, 3) = δN (q0, 3) U δN (q1, 3) U δN (q2,3) U δN (q3, 3) ={q0,q3,,q4} δA ({q0, q2, q3 , q4},1) = U δN (Pi, 1) = δN (q0, 1) U δN (q2, 1) U δN (q3,1) U δN (q4, 1) ={ q0, q1, q2,q3}

δA ({q0, q2, q3 , q4},2) = U δN (Pi, 2) = δN (q0, 2) U δN (q2, 2) U δN (q3,2) U δN (q4, 2) ={ q0,q2, q3,q4} δA ({q0, q2, q3 , q4},3) = U δN (Pi, 3) = δN (q0, 3) U δN (q2, 3) U δN (q3,3) U δN (q4, 3) ={q0,q3,,q4} δA ({q0, q1,q2, q3 , q4},1) = U δN (Pi, 1) = δN (q0, 1) U δN (q1, 1) U δN (q2, 1) U δN (q3,1) U δN (q4, 1) ={ q0, q1, q2,q3,q4} δA ({q0, q1,q2, q3 , q4},2) = U δN (Pi, 2) = δN (q0, 2) U δN (q1, 2) U δN (q2, 2) U δN (q3,2) U δN (q4, 2) ={ q0,q2, q3,q4} δA ({q0, q1,q2, q3 , q4},3) = U δN (Pi, 3) = δN (q0, 3) U δN (q1, 3) U δN (q2, 3) U δN (q3,3) U δN (q4, 3) ={q0,q3,,q4}