TEKNIK KOMPILASI

Soal dan Jawaban VClass1

 Sebutkan  Bahasa  yang terbentuk  dari masing-masing  grammar  berikut :

1. Grammar G1:  

     Vn = {S,A}; Vt ={a,b}; S: Simbol Start;   P = {S  aAa,  A  aAa,  A  b}.

Bahasa L(G1)  = { ?  }

Apakah Grammar G1 dapat digambarkan Finite Automatanya? bila dapat, gambarkan !.

2. Grammar G2:

     Vn = {S,B,C}; Vt = {a,b}; S: Simbol Start;  P = {S  aS,  S  aB,  B  bC,  C  aC,   C  a}.

Bahasa L(G2)  = {  ?  }

Apakah Grammar G2  dapat digambarkan Finite Automatanya? bila dapat, gambarkan!.

3. Grammar G3:

     Vn = {S,A,B}; Vt = {a,b};  S: Simbol Start;  P = {S  bA, A aB,    A  a,  B bA}

Bahasa L(G3)  = {  ?  }

      Apakah Grammar G3  dapat digambarkan  Finite Automatanya?  bila dapat, gambarkan !.

Jawab:

   1.     Tidak bisa digambarkan

Derivasi kalimat terpendek :

S --à aAa(1)

   --à aba(3)

Derivasi kalimat umum:

S-à aAa              (1)

  -à aaAaa          (2)

................

  -à aⁿAaⁿ               (3)

Dari pola kedua kalimat disimpulkan L1(G1 ) = { a n ba n | n ≥ 1} dan tidak bisa digambarkan.

2.     Bisa digambarkan

Derivasi kalimat terpendek :

S ⇒ aB (2)

⇒ abC (3)

⇒ aba (5)

Derivasi kalimat umum :

S ⇒ aS (1)

 …

 ⇒ a n-1S (1)

⇒ a nB (2)

⇒ a nbC (3)

⇒ a n baC (4)

…

⇒ a n ba m-1C (4)

⇒ a n ba m (5)

Dari pola kedua kalimat disimpulkan : L 2 (G 2 ) = { a n ba m | n ≥ 1, m ≥ 1} dan bisa digambarkan seperti dibawah ini

 

  

3    3.      Bisa digambarkan

Derivasi kalimat terpendek

S ⇒ bA (1)

    ⇒ baB (2)

    ⇒ babA (4)

    ⇒ baba (3)

Dari pola ketiga kalimat disimpulkan : L 3 (G 3 ) = {  ba^n   | n ≥ 1} dan bisa digambarkan seperti dibawah ini