Nama : FILIYENSINIM : 11351200054Kelas : TIF4J

QUIZ 2 SEMESTER GENAP 2014/2015

MATA KULIAH TEORI BAHASA DAN OTOMATA (TIF 2412)

1. (Materi : Context Free Grammars – Pohon Penurunan)Sebuah context free frammar G memiliki aturan produksi :

S → aAB

A → Bba

B → bB

B → c

w=acbabc diturunkan sebagai berikut :

S»aAB → a(Bba)B»acbaB»acba(bB) »acbabc

Bangunlah pohon penurunannya!

Jawab:

2. (Materi : Context Free Grammars – Pohon Penurunan)Diberikan CFG dengan G=(N, T, P, S) dimana N={S},T={a},

Tentukan pohon penurunan dari bahasa yang dibangkitkan L(G)!

Jawab:

S»a ,aєL(G)S»SS

»aS

»aa ,a2єL(G)

S»SS»aSS»aaS

»aaa ,a3єL(G)

S»SS»aSSa»aaSa

»aaaa ,a4єL(G)

» a4 ,dan seterusnya

Pohon penurunan sebagai berikut :

Bahasa yang dibangkitkan L(G)={a,aa,aaa,aaaa,.... }atau L(G)={an|n≥1}

3. (Materi : Context Free Grammars – Pohon Penurunan)Tentukan bahasa yang dibangkitkan dari aturan produksi berikut :

S → aS S → aS

S → bS dan S → bS

S → a S → ɛ

Jawab:

S → aS → abS → “aba” dan S → aS → abS → “ab”

4. (Materi : Context Free Grammars – Pohon Penurunan)

Diberikan CFG dengan G=(N, T, P, S) dimana N={S,A}, T={a,b},

Tentukan pohon penurunan dari bahasa yang dibangkitkan L(G)!

Jawab:

S»aS »aaA»aabA

»aabb ,a2b2єL(G)

S»aS »aaSb»aaaAb»aaabAb

»aaabbb ,a3b3єL(G)

» a3b3 ,dan seterusnya

Pohon penurunan sebagai berikut :

Bahasa yang dibangkitkan L(G)={aab,aabb,aaabbb,....} atau L(G)={an,bn|n≥1}

5. (Materi : Context Free Grammars – Pohon Penurunan)

Diberikan CFG dengan :

Tentukan pohon penurunan dari bahasa yang dibangkitkan L(G)!

Jawab:

S»aA »abS»abaA

»abab ,(ab)2єL(G)

S»aA »abaAab»ababSab»ababaAab

»abababab ,(ab)4єL(G)

»(ab)4 ,dan seterusnya

Pohon penurunan sebagai berikut :

Bahasa yang dibangkitkan L(G)={ab,abab,ababab,....} atau

L(G)={(ab)n|n≥1}

6. (Materi : Chomsky Normal Form)Tentukan grammar dari CNF yang ekivalen G, dengan produksi P sebagai berikut: S → aAbBA → aA|aB → bB|b

Jawab:

Aturan produksi yang sudah dalam bentuk normal chomskyA → aB → b

Penggantian aturan produksi kedalam bentuk CNF:

S → aAbB S → P1AP2B P3P4

A → aA → P1A

B → bB → P2B

Terbentuk aturan produksi dari simbol variabel baru:P1 → aP2 → bP3 → P1AP4 → P2B

Hasil akhir aturan produksi dalam bentuk normal chomsky A → aB → bS → P3P4

A → P1AB → P2BP1 → aP2 → bP3 → P1AP4 → P2B

7. (Materi : PDA)

Diberikan L={ambn|n<m}, tentukan CFG yang menerima L

Jawab:

A=({q},{a,b},{S,a,b},δ,q,S,Φ)

δ (q,λ,S)={(q,aSb),(q,aS),(q,a)}

δ(q,a,a) = δ(q,b,b)={(q, λ)}

8. (Materi : Mesin Turing)Apakah konfigurasi mesin turing berikut dapat menerima string ‘000’? Buatlah proses transisinya! Diketahui Q={q0,q1,q2,q3,q4}, Σ={0,1}, Γ={0,1,X,Y,b }, S=q0, F=q4Dengan fungsi transisi sebagai berikut!

δ 0 1 X Y b

q0 (q1,X,R) - - (q3,Y,R) -

q1 (q1,0,R) (q2,Y,L) - (q1,Y,R) -

q2 (q2,0,L) - (q0,X,R) (q2,Y,L) -

q3 - - - (q3,Y,R) (q4,b,L)

q4 - - - - -

Jawab:

String = “000”

Deskripsi :

(q0,000) |- (q1,X00) |- (q1,X00) tidak ada lagi state yang bisa mengalami proses transisi

Konfigurasi :

1. δ (qo,0)=(q1,X,R) pada state q0 head menunjuk karakter ‘X’ menyebabkan head bergerak ke arah kanan

2. δ(q1,0)=(q1,0,R)pada state q1 head menunjuk karakter ‘0’ menyebabkan head bergerak ke arah kanan

3. δ(q1,0)=(q1,0,R)pada state q1 head menunjuk karakter ‘0’ menyebabkan head bergerak ke arah kanan

kesimpulan :

dari state atau simbol yang di tunjuk head tidak ada lagi transisi nya ,berarti mesin turning berhenti yang menyebabkan mesin tersebut tidak dalam keadaan final state, maka dikatakan bahwa input “000” di tolak oleh mesin