Tugas Teknik Kompilasi

1.  dengan   = {1. S → aAa, 2. A → aAa, 3. A → b}.

 Jawab :

Derivasi kalimat terpendek :                                                       Derivasi kalimat umum :

 S ⇒ aAa (1)                                                                                        S ⇒ aAa (1)

    ⇒ aba (3)                                                                                            ⇒ aaAaa (2)

                …

                 ⇒ a n Aa n (2)

               ⇒ a n ba n (3)

Dari pola kedua kalimat disimpulkan := { a n ba n | n ≥ 1}

2. dengan  = {1. S → aS, 2. S → aB, 3. B → bC, 4. C → aC, 5. C → a}.

Jawab :

Derivasi kalimat terpendek :                                                                       Derivasi kalimat umum :

S ⇒ aB (2)                                                                                                            S ⇒ aS                  (1)

⇒ abC (3)                                                                                                                  …

⇒ aba (5)                                                                                                                 ⇒ a n-1S          (1)

                                     ⇒ a n B            (2)

                                ⇒ a n bC          (3)

                                ⇒ a n baC        (4)

                                 …

                                ⇒ a n ba m-1C (4)

                                ⇒ a n ba m      (5)

Dari pola kedua kalimat disimpulkan :  = { a n ba m | n ≥ 1, m ≥ 1}  

3. dengan  = {1. S → bA 2. A → aB, 3. A → a, 4. B → bA}.

Jawab :

Derivasi kalimat terpendek 1:

S ⇒ bA (1)
    ⇒ ba (3)

Finite Automata Derivasi kalimat terpendek:

 

Derivasi kalimat terpendek 2 :

S ⇒ bA (1)

    ⇒ baB (2)

    ⇒ babA (4)

    ⇒ baba (3)

Dari pola ketiga kalimat disimpulkan : L 3 (G 3 ) =