• Teori Bahasa & Otomata


    1. MENGENAL OTOMATA
    1.1. Definisi Otomata

    Otomata adalah mesin abstrak yang dapat mengenali (recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu.

    Sedangkan arti Otomata menurut American Heritage Dictionary:

    1. a robot.

    2. one that behaves in an automatic or mechanical fashion.

    Sementara dalam dunia matematika, Otomata berkaitan dengan teori mesin abstrak, yaitu mesin sekuensial yang menerima input, dan mengeluarkan output, dalam bentuk diskrit. Contoh :

    Mesin Jaja / vending machine.

    Kunci kombinasi.

    Parser/compiler.

    1.2. Pengguna Pertama Istilah Otomata
    Istilah Otomata pertama kali tercantum dalam makalah yang berjudul “The Logical and General Theory of Automata”. Makalah ini ditulis oleh John Von Neumann dari The Institute for Advanced Study dan disajikan di Hixon Simposium pada tanggal 20 September 1948 di Pasadena, Kalifornia, Amerika Serikat.


    1.3. Buku Otomata Pertama
    Sebagai kelanjutan dari makalah tersebut, John Von Neumann menulis buku yang berjudul “Theory of Self-Reproducing Automata”. Buku ini diterbitkan oleh University of Illinois Press pada tahun 1966.

    1.4. Dasar-Dasar Otomata
    Secara garis besar, otomata mempunyai beberapa dasar, yaitu :
    Simbol adalah sebuah entitas abstrak (seperti halnya pengertian titik dalam geometri). Sebuah huruf atau sebuah angka adalah contoh simbol.

    String adalah deretan terbatas (finite) simbol-simbol. Sebagai contoh, jika a, b, dan c adalah tiga buah simbol maka abcb adalah sebuah string yang dibangun dari ketiga simbol tersebut.

    Jika w adalah sebuah string maka panjang string dinyatakan sebagai |w| dan didefinisikan sebagai cacahan (banyaknya) simbol yang menyusun string tersebut. Sebagai contoh, jika w = abcb maka |w| =  4.

    String hampa adalah sebuah string dengan nol buah simbol. String hampa dinyatakan dengan simbol ε (atau ^) sehingga |ε| = 0. String hampa dapat dipandang sebagai simbol hampa karena keduanya tersusun dari nol buah simbol.

    Alfabet adalah hinpunan hingga (finite set) simbol-simbol.

    Operasi Dasar String


    Diberikan dua string : x = abc, dan y = 123
    ·         Prefik string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling belakang dari string w tersebut.
    Contoh : abc, ab, a, dan e adalah semua Prefix(x)
    ·         ProperPrefix string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling belakang dari string w tersebut.
    Contoh : ab, a, dan e adalah semua ProperPrefix(x)
    ·         Postfix (atau Sufix) string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling depan dari string w tersebut.
    Contoh : abc, bc, c, dan e adalah semua Postfix(x)
    ·         ProperPostfix (atau PoperSufix) string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling depan dari string w tersebut.
    Contoh : bc, c, dan e adalah semua ProperPostfix(x)
    ·         Head string w adalah simbol paling depan dari string w.
    Contoh : a adalah Head(x)
    ·         Tail string w adalah string yang dihasilkan dari string w dengan menghilangkan simbol paling depan dari string w tersebut.
    Contoh : bc adalah Tail(x)
    ·         Substring string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling depan dan/atau simbol-simbol paling belakang dari string w tersebut.
    Contoh : abc, ab, bc, a, b, c, dan e adalah semua Substring(x)
    ·         ProperSubstring string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling depan dan/atau simbol-simbol paling belakang dari string w tersebut.
    Contoh : ab, bc, a, b, c, dan e adalah semua Substring(x)
    ·         Subsequence string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol dari string w tersebut.
    Contoh : abc, ab, bc, ac, a, b, c, dan e adalah semua Subsequence(x)
    ·         ProperSubsequence string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol dari string w tersebut.
    Contoh : ab, bc, ac, a, b, c, dan e adalah semua Subsequence(x)
    ·         Concatenation adalah penyambungan dua buah string. Operator concatenation adalah concate atau tanpa lambang apapun.
    Contoh : concate(xy) = xy = abc123
    ·         Alternation adalah pilihan satu di antara dua buah string. Operator alternation adalah alternate atau ½.
    Contoh : alternate(xy) = x½y = abc atau 123
    ·         Kleene Closure : x* = e½x½xx½xxx½… = e½x½x ½x ½

    ·         Positive Closure : x  = x½xx½xxx½… = x½x ½x ½

    Beberapa Sifat Operasi


    ·         Tidak selalu berlaku : x = Prefix(x)Postfix(x).

    ·         Selalu berlaku : x = Head(x)Tail(x).

    ·         Tidak selalu berlaku : Prefix(x) = Postfix(x) atau Prefix(x) ¹ Postfix(x).

    ·         Selalu berlaku : ProperPrefix(x) ¹ ProperPostfix(x).

    ·         Selalu berlaku : Head(x) ¹ Tail(x).

    ·         Setiap Prefix(x), ProperPrefix(x), Postfix(x), ProperPostfix(x), Head(x), dan Tail(x) adalah Substring(x), tetapi tidak sebaliknya.

    ·         Setiap Substring(x) adalah Subsequence(x), tetapi tidak sebaliknya.
    ·         Dua sifat aljabar concatenation :

    ¨      Operasi concatenation bersifat asosiatif : x(yz) = (xy)z.

    ¨      Elemen identitas operasi concatenation adalah e : ex = xe = x.

    ·         Tiga sifat aljabar alternation :

    ¨      Operasi alternation bersifat komutatif : x½y = y½x.

    ¨      Operasi alternation bersifat asosiatif : x½(y½z) = (x½y)½z.

    ¨      Elemen identitas operasi alternation adalah dirinya sendiri : x½x = x.

    ·         Sifat distributif concatenation terhadap alternation : x (y½z) = xy½xz.

    ·         Beberapa kesamaan :

    ¨      Kesamaan ke-1 : (x*)* = x*.

    ¨      Kesamaan ke-2 : e½x  = x ½e = x*.

    ¨      Kesamaan ke-3 : (x½y)* = e½x½y½xx½yy½xy½yx½… = semua string yang merupakan concatenation dari nol atau lebih x, y, atau keduanya.
















    2. FINITE STATE AUTOMATA

    2.1. Definisi

    Finite State Automata dinyatakan oleh 5 tuple  M = (Q , S , d , S , F ).

    Keterangan :

    Q = himpunan state.

    S = himpunan simbol input.

    d = fungsi transisi  d : Q ´ S.

    S = state awal / initial state ,   S Î Q.

    F = state akhir,  F Í Q.

    Contoh :
                    Q = {Genap, Ganjil}
                    S = {0,1}
                    S = Genap
                    F = {Ganjil }
    d
    0
    1

    Genap
    Genap
    Ganjil
         
    Ganjil
    Ganjil
    Genap

    atau
    d(Genap,0) = Genap
    d(Genap,1) = Ganjil
    d(Ganjil,0) = Ganjil
    d(Ganjil,1) = Genap


    Karakteristik dari Finite State Automata sebagai berikut :
    ¨           Model matematika yang dapat menerima input dan mengeluarkan output.

    ¨           Memiliki state yang berhingga banyaknya dan dapat berpindah dari satu state ke state lainnya berdasar input dan fungsi transisi.

    ¨           Tidak memiliki tempat penyimpanan/memori, hanya bisa mengingat state terkini.

    ¨           Mekanisme kerja dapat diaplikasikan pada : elevator, teks editor, analisa leksikal, cek pariti.

    Contoh Cek Pariti ganjil

    Misal :
     1101
    Genap 1 Ganjil 1 Genap 0 Genap 1 Ganjil di terima  oleh mesin.

    Misal :

     

    1100

    Genap 1 Ganjil 1 Genap 0 Genap 0 Genap di tolak oleh mesin.


    2.2. Jenis
    Finite State Automata terdiri atas :
    Deterministic Finite Automata (DFA) : dari suatu state ada tepat satu state berikutnya untuk setiap simbol masukan yang diterima,
    DFA terdiri atas :
    §  Himpunan keadaan (state),
    §  Alfabet atau himpunan huruf,
    §  Satu keadaan awal,
    §  Himpunan keadaan akhir, dan
    §  Fungsi transisi.
    Non-deterministic Finite Automata (NFA) : dari suatu state ada 0, 1 atau lebih state berikutnya untuk setiap simbol masukan yang diterima
    NFA terdiri atas :
    §  Himpunan keadaan (state),
    §  Alfabet atau himpunan huruf,
    §  Satu keadaan awal,
    §  Himpunan keadaan akhir, dan
    §  Relasi transisi.

    Deterministic Finite Automata


    ¨           Contoh :  pengujian pariti ganjil.

    ¨           Contoh lain : pengujian untuk menerima bit string dengan banyaknya 0 genap, serta banyaknya 1 genap.

    ¨           0011 : diterima.
    .
    ¨           10010 : ditolak, karena banyaknya 0 ganjil.

    ¨           Diagram transisi-nya :
    ¨           DFA  sebagai berikut :

                Q = {q0 , q1 , q2 , q3 }
                S = {0,1}
                S = q0
                F = { q0}
    fungsi transisi
    d
    0
    1
    q0
    q2
    q1
    q1
    q3
    q0
    q2
    q0
    q3
    q3
    q1
    q2
       d( q0,011) =  d( q2,11)  = d( q3,1) =  q2                                     Ditolak.
       d( q0,1010) =  d( q1,010)  = d( q3,10)  = d( q2,0) =  q0         Diterima.

    ¨           Contoh lain DFA : Variabel dalam bahasa pascal diawali oleh huruf (besar/kecil), dan diikuti dengan huruf atau angka.
















    ¨           Contoh DFA lainnya :


     

    Nondeterministic Finite Automata


    *  Perbedaan dengan NFA: fungsi transisi dapat memiliki 0 atau lebih fungsi transisi.


    ¨           G = ({q0 , q1 , q2 , q3, q4 }, {0,1}, d ,  q0 , { q2 , q4}}

    d
    0
    1
    q0
    { q0,q3}
    {q0,q1}
    q1
    e
    {q2}
    q2
    {q2}
    {q2}
    q3
    {q4}
    e
    q4
    {q4}
    {q4}
    ¨           String diterima NFA bila terdapat suatu urutan transisi berdasar input, dari state awal ke state akhir.

    ¨           harus mencoba semua kemungkinan.

    ¨           Contoh : string 01001
    * Dua buah FSA disebut ekuivalen apabila kedua FSA tersebut menerima bahasa yang sama
    Contoh : FSA yang menerima bahasa {an | n³0 }

    *  Dua buah state dari FSA disebut indistinguishable  (tidak dapat dibedakan) apabila :
    d(q,w)ÎF sedangkan d(p,w)ÏF dan
    d(q,w) ÏF sedangkan d(p,w) ÎF untuk semua w Î S*
    *  Dua buah state dari FSA disebut distinguishable  (dapat dibedakan) bila terdapat w Î S* sedemikian hingga:
    d(q,w)ÎF sedangkan d(p,w)ÏF dan
    d(q,w) ÏF sedangkan d(p,w) ÎF untuk semua w Î S*
    Prosedur menentukan pasangan status indistinguishable sebagai berikut :
    1.      Hapus semua state yang tak dapat dicapai dari state awal.

    2.      Catat semua pasangan state (p,q) yang distinguishable, yaitu {(p,q) | p Î F Ù q Ï F}.

    3.      Untuk setiap pasangan (p,q) sisanya, untuk setiap aÎ S,  tentukan d(p,a) dan d(q,a).





    Contoh :
    1.      Hapus state yang tidak tercapai -> tidak ada.

    2.      Pasangan distinguishable (q0,q4), (q1,q4), (q2,q4), (q3,q4).

    3.      Pasangan sisanya (q0,q1), (q0,q2), (q0,q3), (q1,q2) (q1,q3) (q2,q3) .

    pasangan
    state 1
    state 2
    Hasil
    0
    1
    0
    1
    (q0,q1)
    q1
    q3
    q2
    q4
    distinguishable
    (q0,q2)
    q1
    q3
    q1
    q4
    distinguishable
    (q1,q2)
    q2
    q4
    q1
    q4
    indistinguishable
    (q0,q3)
    q1
    q3
    q2
    q4
    distinguishable
    (q1,q3)
    q2
    q4
    q2
    q4
    indistinguishable
    (q2,q3)
    q1
    q4
    q2
    q4
    indistinguishable
    Catatan : jumlah pasangan seluruhnya :
    Prosedur Reduksi DFA sebagai berikut :
    1.      Tentukan pasangan status indistinguishable.

    2.      Gabungkan setiap group indistinguishable state ke dalam satu state dengan relasi pembentukan group secara berantai : Jika p dan q indistingishable dan jika q dan r indistinguishable maka p dan r indistinguishable, dan p,q serta r indistinguishable semua berada dalam satu group.

    3.      Sesuaikan transisi dari dan ke state-state gabungan.

    Contoh
    1.      pasangan status indistinguishable (q1,q2), (q1,q3)  dan (q2,q3).

    2.      q1,q2,q3 ketiganya dapat digabung dalam satu state q123.

    3.      Menyesuaikan transisi, sehingga DFA menjadi















    3. Tata Bahasa Bebas Konteks

     

    3.1. Gambaran Bahasa Bebas Konteks

     

    Konsep Dasar


    • Anggota alfabet dinamakan simbol terminal.

    • Kalimat adalah deretan hingga simbol-simbol terminal.

    • Bahasa adalah himpunan kalimat-kalimat. Anggota bahasa bisa tak hingga kalimat.

    • Simbol-simbol berikut adalah simbol terminal :

    ü  huruf kecil, misalnya : a, b, c, 0, 1, …

    ü  simbol operator, misalnya : +, -, dan ´

    ü  simbol tanda baca, misalnya : (,  ),  dan ;

    ü  string yang tercetak tebal, misalnya : if, then, dan else.

    • Simbol-simbol berikut adalah simbol non terminal /Variabel :

    ü  huruf besar, misalnya : A, B, C

    ü  huruf S sebagai simbol awal

    ü  string yang tercetak miring, misalnya : expr .

    • Huruf yunani melambangkan string yang tersusun atas simbol-simbol terminal atau simbol-simbol non terminal atau campuran keduanya, misalnya : a, b, dan g.

    • Sebuah produksi dilambangkan sebagai a ® b, artinya : dalam sebuah derivasi dapat dilakukan penggantian simbol a dengan simbol b.

    • Derivasi adalah proses pembentukan sebuah kalimat atau sentensial. Sebuah derivasi dilambangkan sebagai : a Þ b.

    • Sentensial adalah string yang tersusun atas simbol-simbol terminal atau simbol-simbol non terminal atau campuran keduanya.

    • Kalimat adalah string yang tersusun atas simbol-simbol terminal. Kalimat adalah merupakan sentensial, sebaliknya belum tentu..

    Deskripsi bahasa alami :


     <kalimat>                   ® <subjek> <predikat>

    <subjek>                                 ® <kata benda>

    <predikat>                  ® <kata kerja>

    <kata benda>              ® kucing

    <kata kerja>                ® berlari

    <kata kerja>                ® menyapu


    Contoh  :        

     

    ·         kucing berlari.

                     

    ·         kucing menyapu    (sintaks yes, semantik no).


    Dalam tatabahasa bebas konteks :


    ·         Ruas kiri dari aturan produksi terdiri dari satu simbol non terminal.

    ·         Ruas kanan dapat berupa string yang dibentuk dari simbol terminal dan non  terminal.

    Contoh
    S ®aSb | e
    Kalimat-kalimat yang dibangkitkan dari aturan produksi itu adalah e,ab,aabb,aaabbb,... , anbn

    Contoh
    A ®0A0
    A ®1A1
    A®a
    Kalimat-kalimat yang dibangkitkan dari aturan produksi itu adalah a,01a10, 1001a1001 , 110a011 babR

    Contoh :

    S ® aSb | SS |e

    Bahasa yang dihasilkan oleh tatabahasa dengan aturan produksi di atas adalah :

    L = {w Î (a + b)* |na(w) =nb(w) }

    3.2. Leftmost dan Rightmost Derivation

    Suatu penguraian /penurunan dikatakan leftmost derivation bila setiap tahapan penurunan variabel / non terminal terkiri yang diuraikan. Apabila setiap tahapan penurunan variabel / non terminal paling kanan yang diuraikan disebut rightmost derivation



    Contoh 1 :

    G=({A,B,S}, {a,b},S,P} dengan aturan produksi P :

                S ® AB
                A® aaA | l
    B®Bb | l

    Menspesifikasikan bahasa :

                L(G) = {a2nbm | n³0 , m³0}

    Leftmost derivation untuk menghasilkan string aab

     S Þ AB Þ aaAB Þ aaB Þ aaBb  Þ aab

    Righmost derivation untuk menghasilkan string aab

                S  Þ AB  Þ ABb  Þ aaABb  ÞaaAb  Þaab

    Contoh 2 :

    G=({A,B,S}, {a,b},S,P} dengan aturan produksi P :

                S ® aAB
                A® bBb
    B® A | l

    Leftmost derivation untuk menghasilkan string abbbb

        S Þ aAB Þ abBbB Þ abAbB Þ abbBbbB
           Þ abbbbB Þ abbbb

    Righmost derivation untuk menghasilkan string abbbb

        S  Þ aAB Þ aA Þ abBb Þ abAb Þ abbBbb Þ abbbb

    3.3. Pohon Urai

    Untuk menampilkan penguraian, dapat dilakukan dengan membentuk pohon urai (sayangnya, urutan penguraian tidak terlihat).








    Contoh  :


    3.4. Parsing dan Keanggotaan

    Untuk menentukan apakah string w berada di L(G), dengan cara secara sistematis membangun semua kemungkinan penurunan, dan mencocokkan hasilnya apakah ada yang sama dengan string w.  (disebut exhaustive search parsing)

    Contoh :

    Menentukan apakah string ab berada pada bahasa yang dibentuk oleh grammar dengan aturan produksi S ® SS | aSb | bSa | l.

    Untuk penguraian pertama :

    1. S Þ SS
    2. S Þ aSb
    3. S Þ bSa
    4. S Þ l

    Penguraian nomor 3 dan 4 tidak perlu dilanjutkan. Penguraian 1 dan Penguraian 2 terbentuk sebagai berikut :

    1a. S Þ SS Þ SSS                             2a. S Þ aSb Þ aSSb
    1b. S Þ SS Þ aSbS                           2b. S Þ aSb Þ aaSbb
    1c. S Þ SS Þ bSaS                           2c. S Þ aSb Þ abSab
    1d. S Þ SS Þ S                                 2d. S Þ aSb Þ ab

    3.5. Ambiguitas pada Tatabahasa dan Bahasa

    Tatabahasa bebas konteks G disebut ambigu jika terdapat beberapa w Î L(G) yang mempunyai paling sedikit dua buah pohon penurunan

    Contoh :

    Tatabahasa dengan aturan produksi S ® SS | aSb | l.

    string aabb mempunyai 2 pohon penurunan :
     

    3.6. Pumping Lemma untuk bahasa bebas konteks

    ¨        Jika suatu rangkaian simbol / string yang cukup panjang yang merupakan sebuah bahasa bebas konteks, maka kita dapat menemukan dua substring yang jaraknya berdekatan yang jika dipompa, string baru yang diperoleh merupakan bahasa bebas konteks juga.

    ¨        Secara formal, lemma di atas dinyatakan dengan


    ¨        Syarat “ kedua lokasi berdekatan” dinyatakan dengan kondisi |vwx| £ n.

    ¨        Jika salah satu v atau x diambil sebagai string kosong, maka lemma diatas berubah menjadi lemma untuk bahasa reguler

    Contoh :

    Tatabahasa dengan aturan produksi

    S  ®uAy
    A ® vAx
    A ® w


    maka aturan derivasinya sebagai berikut :

    S Þ uAy Þ uwy
    S Þ uAy Þ uvAxy Þuvwxy
    S Þ uAy Þ uvAxy Þ uvvAxxy Þuvvwxxy

    sehingga untuk setiap i ³0 , uviwxiy Î L.

     3.7. Sifat sifat tertutup bahasa bebas konteks

    ¨        Gabungan  dua CFL merupakan CFL juga.

    Jika diketahui dua buah CFG G1= (N1,T1,S1,P1) dan G2=(N2,T2,S2,P2) yang menghasilkan bahasa L1 dan L2 ,  maka CFG L1 È L2 dapat dibentuk dengan cara :
    1.      Menggabungkan kedua himpunan dan menambahkan satu simbol variabel baru S

    2.      Menggabungkan kedua himpunan simbol terminal

    3.      Menggabungkan kedua himpunan aturan produksi dan menambahkan satu aturan produksi baru

    S ® S1|S2 yang digunakan untuk memilih salah satu simbol awal S1 atau S2 dari simbol awal baru S
    G3 = (N1ÈN2­È{S},T1ÈT2 ,S,P1ÈP2 È{S®S1|S2}}
    ¨        Penyambungan dua CFL merupakan CFL juga.

    Jika diketahui dua buah CFG G1= (N1,T1,S1,P1) dan G2=(N2,T2,S2,P2) yang menghasilkan bahasa L1 dan L2 ,  maka bahasa L1L2 dapat dibentuk oleh :
    G4 = (N1ÈN2­È{S},T1ÈT2 ,S,P1ÈP2 È{S®S1S2}}
    ¨        Klosure Kleene dari CFL adalah CFL juga.

    Klosure Kleene dari tatabahasa G=(N,T,S1,P) adalah
    G5 = (N È {S} , T , S , P È {S ® S1S | e } )
    ¨        Bahasa bebas konteks tertutup terhadap substitusi

    Contoh :
    La = {0 n1n | n ³1 } dan Lb = { wwR | w Î (0+2)* }
    dihasilkan oleh tatabahasa Ga dengan aturan produksi
          Sa ® 0Sa1 | 01 serta tatabahasa G2 dengan aturan produksi Sb ® 0Sb0 | 2Sb2 | e.

    Didefinisikan tatabahasa G dengan aturan produksi S ® aSbS | bSaS | e


    Jika f adalah substitusi f(a)= La dan f(b) = Lb maka  f(L) adalah bahasa yang dihasilkan oleh tatabahasa dengan aturan produksi :
          S ® SaSSbS | SbSSaS | e
          Sa ® 0Sa1 | 01

          Sb ® 0Sb0 | 2Sb2 | e

    Tatabahasa Bebas Konteks dan Bahasa Pemrograman


    ¨        Tatabahasa bebas konteks digunakan untuk mendefinisikan sintaks bahasa pemrograman.

    ¨        Menggunakan notasi BNF (Backus-Naur Form).

    ¨        Variabel / non terminal :  <...> .

    ¨        Terminal : tanpa tanda.

    ¨        ¬ diganti dengan ::=

    ¨        Contoh :

    Statement  if then else

    < if_statement> ::= if <expression>
    <then_clause>
    <else_clause>










    4. PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS

    4.1. Tujuan
    Melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tidak perlu atau aturan produksi yang tidak berarti.
    Contoh 1 :
    S à AB | a
    Aàa
    ¨           Aturan produksi S à AB tidak berarti karena B tidak memiliki penurunan

    Contoh 2 :
                    SàA
    AàB
    BàC
    CàD
    D à a | A
    ¨           Memiliki kelemahan terlalu panjang jalannya padahal berujung pada S à a,

    ¨           produksi  D à A juga menyebabkan kerumitan.

    Cara Penyederhanaan:
    1. Penghilangan produksi useless ( tidak berguna ).

    1. Penghilangan produksi unit.

    1. Penghilangan produksi ε .

    4.2. Penghilangan Produksi Useless
    Di sini produksi useless didefinisikan sebagai :
    ·                     Produksi yang memuat simbol variabel yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya.

    ·                     Produksi yang tidak akan pernah dicapai dengan penurunan apapun dari simbol awal, sehingga produksi itu redundan ( berlebih ).

    Contoh :
    S à aSa | Abd | Bde
    A à Ada
    Bà BBB | a
    Maka
    1)      Simbol variabel A tidak memiliki penurunan yang menuju terminal, sehingga bisa dihilangkan

    2)      Konsekuensi no (1), aturan produksi S à Abd tidak memiliki penurunan

    Penyederhanaan menjadi:
    SàaSa | Bde
    Bà BBB | a
    Contoh :
    Sà Aa | B
    Aàab | D
    Bà b | E
    Cà bb
    Eà aEa
    Maka :
    §  Aturan produksi A à D, simbol variabel D tidak memiliki penurunan.

    §  Aturan produksi C à bb, Penurunan dari simbol S, dengan jalan manapun tidak akan pernah mencapai C.

    §  Simbol variabel E tidak memiliki aturan produksi yang menuju terminal.           

    §  Konsekuensi no (3) Aturan produksi B à E, simbol variabel E tidak memiliki penurunan.

    §  Produksi yang useless:
    A à D
    C à bb
    E à aEa
    B à E
    Penyederhanaannya menjadi:
    S à Aa | B
    A à ab
    B à b
    Contoh :
                    S à aAb | cEB
    A à dBE | eeC
    B à ff
    C à ae
    D à h
    Analisa :
    1)      Aturan produksi S à cEB, A à dBE dapat dihilangkan ( E tidak memiliki penurunan).

    2)      Aturan produksi D à h, redundan

    Sisa aturan produksi
    S à aAb
    A à eeC
    B à ff
    C à ae
    Analisis lagi
                    B à ff juga redundan,
    Hasil penyederhanaan menjadi:
    S à aAb
    A à eeC
    C à ae
    Contoh lain lagi :
    S à aB
    A à bcD | dAC
    B à e | Ab
    C à bCb | adF | ab
    F à cFB
    Analisa :
    1)      Aturan produksi A à bcD, variabel D tidak memiliki penurunan.

    2)       Konsekuensi no (1), simbol variabel A tidak memiliki penurunan yang menuju terminal (tinggal A à dAC).

    3)      Konsekuensi no (2),  B à Ab tidak memiliki penurunan.

    4)      Simbol variabel F tidak memiliki penurunan yang menuju terminal.

    5)      Konsekuensi no (4), C à adF tidak memiliki penurunan

    Setelah disederhanakan menjadi:
    S à aB
    B à e
    C à bCb | ab
    Contoh  :
    S à aBD
    B à cD | Ab
    D à ef
    A à Ed
    F à dc
    Analisa :
    1)      Aturan produksi A à Ed, E tidak memiliki penurunan.

    2)      Aturan produksi F à dc, redundan.

    Sisa aturan produksi:
    S à aBD
    B à cD | Ab
    D à ef
    Analisa lagi
                    B à Ab, A tidak memiliki penurunan.
    Hasil penyederhanaan:
    S à aBD
    B à cD
    D à ef
    Contoh lagi:
    S à Abc | ab
    A à AAA | ε
    Aturan produksi setelah disederhanakan:
    S à Abc | ab
    A à AAA | ε
    Ingat A à ε juga harus diperhitungkan

    PRINSIP


    Setiap kali melakukan penyederhanaan diperiksa lagi aturan produksi yang tersisa, apakah semua produksi yang useless sudah hilang.
    Penghilangan Produksi Unit
    ¨           Produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu simbol variabel, misalkan: A à B, C à D.

    ¨           Keberadaannya membuat tata bahasa memiliki kerumitan yang tak perlu.

    ¨           Penyederhanaan dilakukan dengan melakukan penggantian aturan produksi unit.

    Contoh:
    S à Sb
    S à C
    C à D
    C à ef
    D à dd
    Dilakukan penggantian berturutan mulai dari aturan produksi yang paling dekat menuju ke penurunan terminal-terminal (‘=>’ dibaca ‘menjadi’):
    ·                     C à D => C à dd

    ·                     S à C => S à dd | ef

    Sehingga aturan produksi setelah penyederhanaan:
    S à Sb
    S à dd | ef
    C à dd
    C à ef
    D à dd
    Contoh :
    S à A
    S à Aa
    A à B
    B à C
    B à b
    C à D
    C à ab
    D à b
    Penggantian yang dilakukan :
    ·                     C à D => C à b

    ·                     B à C => B à b | ab, karena B à b sudah ada, maka cukup dituliskan B à ab

    ·                     A à B => A à ab | b

    ·                     S à A => ab | b

    Sehingga aturan produksi setelah penyederhanaan:
    S à ab | b
    S à Aa
    A à ab | b
    B à ab
    B à b
    C à b
    C à ab
    D à b
    Contoh :
    S à Cba | D
    A à bbC
    B à Sc | ddd
    C à eAn | f | C
    D à E | SABC
    E à gh
    Penggantian yang dilakukan:
    ·                     D à E menjadi D à gh

    ·                     C à C , kita hapus

    ·                     S à D menjadi S à gh | SABC

    Sehingga aturan produksi setelah penyederhanaan:
    S à Cba | gh | SABC
    A à bbC
    B à Sc | ddd
    C à eA | f
    D à gh | SABC
    E à gh
    Penghilangan Produksi ε
                    Produksi ε adalah produksi dalam bentuk
    α à ε
    atau bisa dianggap sebagai produksi kosong ( empty ). Penghilangan produksi ε dilakukan dengan melakukan penggantian produksi yang memuat variabel yang bisa menuju produksi ε, atau biasa disebut nullable. Prinsip penggantiannya bisa dilihat kasus berikut :
    S à bcAd
    A à ε
    A nullable serta A à ε satu-satunya produksi dari A, maka variabel A bisa ditiadakan, hasil penyederhanaan tata bahasa bebas konteks menjadi:
    S à bcd
    Tetapi bila kasusnya:
    S à bcAd
    A à bd | ε
    A nullable, tapi A à ε bukan satu-satunya produksi dari A, maka hasil penyederhanaan:
    S à bcAd | bcd
    A à bd
    Contoh lagi, terdapat tata bahasa bebas konteks:
    S à Ab | Cd
    A à d
    C à ε
    Variabel yang nullable  adalah variabel C. Karena penurunan C à ε merupakan penurunan satu-satunya dari C, maka kita ganti S à Cd menjadi S à d. Kemudian produksi C à ε kita hapus.
    Setelah penyederhanaan menjadi :
    S à Ab | d
    A à d
    Contoh :
    S à dA | Bd
    A à bc
    A à ε
    B à c
    Variabel yang nullable adalah variabel A. A à ε bukan penurunan satu-satunya dari A ( terdapat A à bc ), maka kita ganti S à dA menjadi S à dA | d.A à ε kita hapus.
    Setelah penyederhanaan :
    S à dA | d | Bd
    A à bc
    B à c
    Contoh tata bahasa bebas konteks:
    S à AaCD
    A à CD | AB
    B à b | ε
    C à d | ε
    D à ε
    Variabel yang nullable adalah variabel B, C, D. Kemudian dari  A à CD, maka variabel A juga nullable ( A à ε ). Karena D hanya memilki penurunan D à ε, maka kita sederhanakan dulu:
    S à AaCD => S à AaC
    A à CD => A à C
    D à ε kita hapus

    Selanjutnya kita lihat variabel B dan C memiliki penurunan ε, meskipun bukan satu-satunya penurunan, maka dilakukan penggantian:
    ·                     A à AB => A à AB | A | B
    ·                     S à AaC => S à AaC | aC | Aa | a
    ·                     B à ε dan C à ε kita hapus
    Setelah penyederhanaan:
    S à AaC | aC | Aa | a
    A à C | AB | A | B
    B à b
    C à ε
    Variabel yang nullable adalah A, B, C. Dari S à AB, maka S juga nullable. Kita lakukan penggantian:
    A à aCa => A à aa
    B à bA => B à bA | b
    B à BB => B à BB | B
    A à abB => A à abB | ab
    S à AB => S à AB | A | B | ε
    C à ε, B à ε, A à ε dihapus

    * Perhatikan untuk penggantian S à AB kita tetap mempertahankan S à ε, karena S merupakan simbol awal. Ini merupakan satu-satunya perkecualian produksi ε yang tidak dihapus, yaitu produksi ε yang dihasilkan oleh simbol awal.
    Hasil akhir dari penyederhanaan:
    S à AB | A | B | ε
    A à abB | ab | aa
    B à bA | b | BB | B
    Contoh :
    Tata bahasa bebas konteks :
    S à aAb
    A à aAb | ε
    Hasil penyederhanaan :
    S à aAb | ab
    A à aAb | ab
    Contoh :
    Tata bahasa bebas konteks :
    S à ABaC
    A à BC
    B à b | ε
    C à D | ε
    D à d

    Hasil penyederhanaan:
    S à ABaC | BaC | AaC | ABa | aC | Aa | Ba | a
    A à B | C | BC
    B à b
    C à D
    D à d
    Prakteknya ketiga penyederhanaan tersebut  dilakukan bersama pada suatu tata bahasa bebas konteks, yang nantinya menyiapkan tata bahasa bebas konteks tersebut untuk diubah kedalam suatu bentuk normal Chomsky.
    Urutan penghapusan aturan produksi :
    1)      Hilangkan produksi ε

    2)      Hilangkan produksi unit

    3)      Hilangkan produksi useless

    Contoh :
    S à AA | C | bd
    A à Bb | ε
    B à AB | d
    C à de
    Hilangkan produksi ε, sehingga menjadi:
    S à A | AA | C | bd
    A à Bb
    B à B | AB | d
    C à de
    Selanjutnya penghilangan produksi unit menjadi:
    S à Bb | AA | de | bd
    A à Bb
    B à AB | d
    C à de

    Penghilangan produksi unit bisa menghasilkan produksi useless.  Terakhir dilakukan penghilangan produksi useless:
    S à Bb | AA | de | bd
    A à Bb
    B à AB | d
    Hasil akhir aturan produksi tidak lagi memiliki produksi ε, produksi unit, maupun produksi useless.




    5. BENTUK NORMAL CHOMSKY

    5.1. Definisi Bentuk Normal Chomsky
    Bentuk normal Chomsky / Chomsky Normal Form  (CNF) merupakan salah satu bentuk normal yang sangat berguna untuk tata bahasa bebas konteks ( CFG ). Bentuk normal Chomsky dapat dibuat dari sebuah tata bahasa bebas konteks yang telah mengalami penyederhanaan yaitu penghilangan produksi useless, unit, dan ε. Dengan kata lain, suatu tata bahasa bebas konteks dapat dibuat menjadi bentuk normal Chomsky dengan syarat tata bahasa bebas konteks tersebut:
    ·                     Tidak memiliki produksi useless

    ·                     Tidak memiliki produksi unit

    ·                     Tidak memiliki produksi ε

    Aturan produksi dalam  bentuk normal Chomsky ruas kanannya tepat berupa sebuah terminal atau dua variabel. Misal :
    A à BC
    A à b
    B à a
    C à BA | d
    Pembentukan Bentuk Normal Chomsky
    Langkah-langkah pembentukan  bentuk normal Chomsky  secara umum sebagai berikut:
    ·                     Biarkan aturan produksi yang sudah dalam  bentuk normal Chomsky .

    ·                     Lakukan penggantian aturan produksi yang ruas kanannya memuat simbol terminal dan panjang ruas kanan > 1.

    ·                     Lakukan penggantian aturan produksi yang ruas kanannya memuat > 2 simbol variabel.

    ·                     Penggantian-penggantian tersebut bisa dilakukan berkali-kali sampai akhirnya semua aturan produksi dalam  bentuk normal Chomsky  .

    ·                     Selama dilakukan penggantian, kemungkinan kita akan memperoleh aturan-aturan produksi baru, dan juga memunculkan simbol-simbol variabel baru


    Contoh, tata bahasa bebas konteks ( kita anggap tata bahasa bebas konteks pada bab ini sudah mengalami penyederhanaan ) :

    S à bA | aB
    A à bAA | aS | a
    B à aBB | bS | b

    Aturan produksi yang sudah dalam  bentuk normal Chomsky :

    A à a
    B à b

    Dilakukan penggantian aturan produksi yang belum bentuk normal Chomsky (‘=>’ bisa dibaca berubah menjadi) :

    S à bA => S à P1A
    S à aB => S à P1B
    A à bAA => S à P1AA => A à P1P3
    A à aS => A à P2S
    B à aBB => B à P2BB => B à P2P4
    B à bS => B à P1S
    Terbentuk aturan produksi dan simbol variabel baru :
    P1 à b
    P2 à a
    P3 à AA
    P4 à BB
    Hasil akhir aturan produksi dalam bentuk normal Chomsky :

    A à a
    B à b
    S à P1A
    S à P2B
    A à P1P3
    A à P2S
    B à P2P4
    B à P1S
    P1 à b
    P2 à a
    P3 à AA
    P4 à BB

    Contoh, tata bahasa bebas konteks:

    S à aB | CA
    A à a | bc
    B à BC | Ab
    C à aB | b
    Aturan produksi yang sudah dalam bentuk normal Chomsky :

    S à CA
    A à a
    B à BC
    C à b

    Penggantian aturan produksi yang belum dalam bentuk normal Chomsky :

    S à aB => S à P1B
    A à bc => S à P2P3
    B à Ab => B à A P2
    C à aB => C à P1B

    Terbentuk aturan produksi dan simbol variabel baru :

    P1 à a
    P2 à b
    P3 à c

    Hasil akhir aturan produksi dalam  bentuk normal Chomsky :

    S à CA
    A à a
    B à BC
    C à b
    S à P1B
    S à P2P3
    B à A P2
    C à P1B
    P1 à a
    P2 à b
    P3 à c
    Contoh :
    Tata bahasa bebas konteks  :
    S à aAB | ch | CD
    A à dbE | eEC
    B à ff | DD
    C à ADB | aS
    D à i
    E à jD
    Aturan produksi yang sudah dalam bentuk normal Chomsky :
    S à CD
    B à DD
    D à  i


    Penggantian aturan produksi:
    S à aAB => S à P1P2
    S à ch => S à P3P4
    A à dbE => A à P5P6
    A à eEC => A à P8P9
    B à ff => B à P10P10
    C à ADB => C à AP11
    C à aS => C à P1S
    E à jD => E à P12D
    Terbentuk aturan produksi baru:
    P1 à a
    P2 à AB
    P3 à c
    P4 à h
    P5 à d
    P6 à P7E
    P7 à b
    P8 à e
    P9 à EC
    P10 à f
    P11 à DB
    P12 à j
    Hasil akhir dalam bentuk normal Chomsky:
    S à CD
    B à DD
    D à i
    S à P1P2
    S à P3P4
    A à P5P6
    A à P8P9
    B à P10P10
    C à AP11
    C à P1S
    E à P12D
    P1 à a
    P2 à AB
    P3 à c
    P4 à h
    P5 à d
    P6 à P7E
    P7 à b
    P8 à e
    P9 à EC
    P10 à f
    P11 à DB
    P12 à j
    4.2. Algoritma CYK untuk Tata Bahasa Bebas Konteks
    Algoritma CYK merupakan algoritma parsing dan keanggotaan ( membership) untuk tata bahasa bebas konteks. Algortima ini diciptakan oleh J. Cocke, DH. Younger, dan T. Kasami. Syarat untuk penggunaan algortima ini adalah tata bahasa harus berada dalam  bentuk normal Chomsky . Obyektivitas dari algortima ini untuk menunjukkan apakah suatu  string dapat diperoleh dari suatu tata bahasa.
    Algoritma CYK sebagai berikut:
    begin
    1)  for i:= 1 to n do
    2)  Vi1 := {A| A à a aturan produksi dimana simbol ke- i adalah a };
    3)  for j:= 2 to n do
    4)      for i:= 1 to (n-j+1) do
    begin
    5)             Vij:=Ø;
    6)             for k:=1 to (j – 1) do
    7)                  Vij:= Vij υ ( A | A à BC adalah suatu produksi, dimana B di Vik dan C di Vi+k,j-k }
    end
    end
    Penjelasan:
    ·                     n = panjang untai yang akan diperiksa, missal : untuk untai ‘ada’, n = | ada | =3

    ·                     i  akan menyatakan kolom ke-

    ·                     j  akan menyatakan baris ke-

    ·                     tahapan no (1) dan (2) untuk mengisi table baris pertama kolom 1 – n

    ·                      no (3), interasi dari baris ke- 2 sampai n

    ·                     no (4), interasi untuk mengisi kolom 1 sampai ( n – baris + 1) pada suatu baris.

    ·                     no (5) inisialisasi  Vij dengan Ø

    ·                      no (6) dan no (7), interasi untuk memeriksa mana saja yang menjadi anggota Vij


                   



                   






    6. PENGHILANGAN REKURSIF KIRI

    6.1. Aturan Produksi Rekursif
                   
    Aturan  Produksi yang rekursif memilki ruas kanan (hasil produksi) yang memuat simbol variabel pada ruas kiri. Sebuah aturan produksi dalam bentuk : A à βA merupakan aturan produksi yang rekursif kanan.

    Keterangan :

    β=(VÈT)* atau kumpulan simbol variabel dan terminal
    Contoh aturan produksi yang rekursif kanan:
    S à dS
    B à adB
    Produksi dalam bentuk:
    A à
    Merupakan aturan produksi yang rekursif kiri,
    Contoh :
    S è Sd
    B à Bad
    Produksi yang rekursif kanan menyebabkan pohon penurunan tumbuh ke kanan, sebaliknya Produksi yang rekursif kiri menyebabkan pohon penurunan tumbuh ke kiri.
    Dalam banyak penerapan tata bahasa, rekursif kiri tak diinginkan. Untuk menghindari penurunan yang bisa mengakibatkan loop kita perlu menghilangkan sifat rekursif kiri dari aturan produksi. Penghilangan rekursif kiri disini memungkinkan suatu tata bahasa bebas konteks nantinya diubah ke dalam bentuk normal Greibach.
    6.2. Tahapan Penghilangan Rekursif Kiri
    Langkah-langkah penghilangan rekursif kiri sebagai berikut :
    §     Pisahkan aturan produksi yang rekursif kiri dan yang tidak, missal :



    Aturan produksi yang rekursif kiri :
    A à1 | Aα2 | Aα3 | ....... Aαn  
    Aturan produksi yang tidak rekursif kiri (termasuk produksi ε) :
    A à β1 | β2 | β3 | ........ βm
         
    §  Dari situ kita bisa tentukan α1, α2, .... αn,  dan β1, β2, .... βm  dari setiap aturan produksi yang memiliki simbol ruas kiri yang sama.

    §  Lakukan penggantian aturan produksi yang rekursif kiri, menjadi sebagai berikut:

    ü  A à β1Z | β2Z | .... βmZ
    ü  Z à  α1 | α2  | α3 | .... αn
    ü  Z à α1Z | α2Z | α3Z | .... αnZ

    Penggantian diatas dilakukan untuk setiap aturan produksi dengan simbol ruas kiri yang sama. Bisa muncul simbol variabel baru Z1, Z2 dan seterusnya, sesuai banyaknya variabel yang menghasilkan produksi yang rekursif kiri.
    §  Hasil akhir berupa aturan produksi pengganti ditambah dengan aturan produksi semula yang tidak rekursif kiri.

    Contoh :
    Ttata bahasa bebas konteks :
    S à Sab | aSc |dd | ff | Sbd

    Pertama-tama kita lakukan pemisahan aturan produksi
    Aturan produksi yang rekursif kiri : S à Sab | Sbd
    Dari situ kita tentukan :
    Untuk simbol ruas kiri sebagai berikut S : α1 = ab, α2 = bd
    Aturan produksi yang tidak rekursif kiri : S à aSc | dd | ff
    Dari situ kita dapatkan:
    Untuk simbol ruas kiri sebagai berikut : S : β1 = aSc, β2 = dd, β3 = ff
    Kita lakukan penggantian aturan produksi yang rekursif kiri:
    Untuk yang memiliki simbol ruas kiri S:
    S à Sab | Sbd, digantikan oleh:
    S à aScZ1 | dd Z1 | ffZ1
    Z1 à ab | bd
    Z1 à abZ1 | bd Z1

    Hasil akhir setelah penghilangan rekursif kiri adalah:

    S à aSc | dd | ff
    S à aScZ1 | dd Z1 | ffZ1
    Z1 à ab | bd
    Z1 à abZ1 | bd Z1
    Pada kasus di atas S adalah satu-satunya simbol variabel yang menghasilkan produksi rekursif kiri.
    Contoh lain, terdapat tata bahasa bebas konteks:
    S à Sab | Sb | cA
    A à Aa | a | bd
    Pertama-tama kita lakukan pemisahan aturan produksi
    Aturan produksi yang rekursif kiri :
    S à Sab | Sb
    A à Aa
    Dari situ kita tentukan:
    Untuk simbol ruas kiri S: α1= ab, α2 =b
    Untuk simbol ruas kiri A: α1 = a
    Aturan produksi yang tidak rekursif kiri :
    S à cA
    A à a | bd
    Dari situ kita dapatkan
    Untuk simbol ruas kiri S: β1 = cA
    Untuk simbol  ruas kiri A: β1 = a, β2 = bd
    Kita lakukan penggantian aturan produksi yang rekursif kiri:
    Untuk yang memiliki simbol ruas kiri S :
    S à Sab | Sb, digantikan oleh :

    S à cAZ1
    Z1 à ab | b
    Z1 à abZ1 | bZ1

    Untuk yang memiliki simbol ruas kiri A :

    A à Aa, digantikan oleh:
    A à a Z2 | bdZ2
    Z2 à a
    Z2 à a Z2

    Hasil akhir setelah penghilangan rekursif kiri adalah:
    S à cA
    A à a | bd
    S à cAZ1
    Z1 à ab | b
    Z1 à abZ1 | bZ1
    A à a Z2 | bdZ2
    Z2 à a
    Z2 à a Z2
    Perhatikan bahwa penghilangan rekursif kiri memunculkan simbol variabel baru, dan aturan produksi baru yang rekursif kanan.
    Contoh lain, terdapat tata bahasa bebas konteks:
    S à Sa |aAc | c | ε
    A à Ab | ba
    Pertama-tama kita lakukan pemisahan aturan produksi
    Aturan produksi yang rekursif kiri:
    S à Sa
    A à Ab
    Dari situ kita tentukan:
    Untuk simbol ruas kiri S: α1 = a
    Untuk simbol ruas kiri A: α1 = b
    Aturan produksi yang tidak rekursif kiri:
    S à aAc | c | ε
    A à ba
    Dari situ kita dapatkan
    untuk simbol ruas kiri S:β1 = aAc, β2= c, β3 = ε
    untuk simbol ruas kiri A: β1 = ba
    Perhatikan produksi ε termasuk produksi yang tidak rekursif kiri
    Kita lakukan penggantian aturan produksi yang rekursif kiri :
    Untuk yang memilki simbol ruas kiri S :
    S à Sa, digantikan oleh :
    S à aAcZ1 | cZ1 | Z1
    Z1 à a
    Z1 à a Z1

    Untuk yang memiliki simbol ruas kiri A:
    A à Ab, digantikan oleh :
    A à ba Z2
    Z2 à b
    Z2 à bZ2

    Hasil akhir setelah penghilangan rekursif kiri adalah:

    S à aAc | c | ε
    S à aAcZ1 | cZ1 | Z1
    A à ba
    A à ba Z2
    Z1 à a
    Z1 à a Z1
    Z2 à b
    Z2 à b Z2

    7. BENTUK NORMAL GREIBACH

    7.1. Definisi Bentuk Normal Greibach
    Bentuk normal Greibach merupakan bentuk normal yang memiliki banyak konsekuensi teoritis dan prkatis. Dalam bentuk normal Greibach  kita membatasi posisi munculnya terminal-terminal dan variabel-variabel. Suatu tata bahasa bebas konteks (CFG) dikatakan dalam bentuk normal Greibach / Greibach Normal Form,  selanjutnya kita sebut sebagai GNF, jika setiap aturan produksinya ada dalam bentuk:
    A à
    Keterangan :
    A : simbol terminal (tunggal), a ε T
    Α : rangkaian simbol-simbol variabel (V*)
    Atau dengan kata lain, suatu tata bahasa bebas konteks dalam bentuk normal Greibach bila hasil produksinya (ruas kanan) diawali dengan satu simbol terminal, slanjutnya bisa diikuti oleh rangkaian simbol variabel. Contoh tata bahasa bebas konteks dalam bentuk  bentuk normal Greibach:
     S à a | aAB
    A à aB
    B à cS
    Untuk dapat diubah ke dalam bentuk normaol Greibach, tata bahasa semula haru memenuhi syarat:
    • Sudah dalam bentuk normal Chomsky
    • Tidak bersifat rekursif kiri
    • Tidak menghasilkan ε

    Terdapat dua cara pembentukan bentuk normal Greibach , yaitu melalui substitusi dan perkalian matriks. Pada bagian berikutnya kita membahasa kedua cara tersebut.
    7.2. Pembentukan Bentuk Normal Greibach dengan Substitusi
    Secara umum langkah-langkah untuk mendapatkan bentuk normal Greibach :
    1.              Tentukan urutan simbol-simbol variabel yang ada dalam tata bahasa. Misalkan terdapat m variabel dengan urutan A1, A2, ...., Am

    2.            Berdasarkan urutan simbol yang ditetapkan pada langkah (1) seluruh aturan produksi yang ruas kanannya diawali dengan simbol variabel dapat dituliskan dalam bentuk Ah à Ai γ di mana h <> i (rekrusif kiri sudah dihilangkan), γ bisa berupa simbol-simbol variabel :
    a.             Jika h < i, aturan produksu ini sudah benar ( tidakperlu diubah)

    b.            Jika h > i, aturan produksi belum benar. Lakukan substitusi berulang-ulang terhadap Ai (ganti Ai pada produksi ini dengan ruas kanan produksi dari variabel Ai ) sehingga suatu saat diperoleh produksi dalam bentuk Ah à Ap γ (dimana h £ p )
    i)        Jika h = p , lakukan penghilangan rekursif kiri
    ii)       Jika h < p, aturan produksi sudah benar  
          
    3.            Jika terjadi penghilangan rekursif kiri pada tahap (2b), sejumlah simbol variabel baru yang muncul dari operasi ini dapat disisipkan pada urutan variabelsemula dimana saja asalkan ditempatkan tidak sebelum Ah (di kiri)

    4.            Setelah langkah (2) & (3) dikerjakan maka aturan-aturan produksi yang ruas kanannya dimulai simbol variabel sudah berada dalam urutan yang benar
    Ax à Ay g ( di mana x < y )
    Produksi-produksi yang lain ada dalam bentuk:
    Ax à a g ( a = simbol terminal )
    Bx à g
    ( B2 = simbol variabel baru yang akan muncul sebagai akibat dari operasi penghilangan rekursif kiri ).
    5.            Bentuk normal Greibach  diperoleh dengan cara melakukan substitusi mundur mulai dari variabel Am, lalu Am-1, Am-2, ..... Dengan cara ini aturan produksi dalam bentuk Ax à Ay g dapat diubah sehinga ruas kanannya dimulai dengan simbol terminal.

    6.            Produksi dalam bentuk Bx à g juga dapat diubah dengan cara substitusi seperti pada langkah (5).

    Contoh (tata bahasa bebas konteks sudah dalam bentuk normal Chomsky dan memenuhi syarat untuk diubah ke bentuk normal Greibach), simbol awal adalah S:
    S à CA
    A à a | d
    B à b
    C à DD
    D à AB
    Kita tentukan urutan simbol variabel, misalnya S, A, B, C, D (S<A<B<C<D).
    * Perhatikan urutan tersebut boleh anda tentukan sendiri, buatlah urutan sedemikian sehingga memudahkan untuk proses selanjutnya

    Kita periksa aturan produksi yang simbol pertama pada ruas kanan adalah simbol variabel, apakah sudah memenuhi ketentuan urutan variabel:
    §  S à CA ( sudah memenuhi aturan karena S<C)

    §  C à DD (sudah memenuhi karena C<D)

    §  D à AB (tidak memenuhi, karena D>A)

    Yang belum memenuhi urutan yang telah kita tentukan adalah: D à AB, karena ruas kiri > simbol pertama pada ruas kanan. Maka kita lakukan sibstitusi pada simbol variabel A, aturan produksi menjadi :
    D à aB | dB
    Setelah semua aturan produksi sudah memenuhi ketentuan urutan variabel, kita lakukan substitusi mundur pada aturan produksi yang belum dalam bentuk normal Greibach  (‘=>’ dibaca ‘menjadi’):

    §  C à DD => C à aBD | dBD

    §  S à CA => S à aBDA | dBDA

    * Perhatikan substitusi mundur dimulai dari aturan produksi yang memiliki ruas kiri dengan urutan variabel paling akhir ( kasus di atas:S<A<B<C<D, maka C lebih dulu disubstitusikan daripada S ).
    Hasil akhir aturan produksi yang sudah dalam bentuk normal Greibach :
    S à aBDA | dBDA
    A à a | d
    B à b
    C à aBD | dBD
    D à aB | dB
    * Perhatikan : setiap substitusi kita lakukan pada simbol variabel pertamapada ruas kanan ( pada aturan produksi yang belum bentuk normal Greibach tentunya ).
    Prinsipnya :
    • Biarkan aturan produksi yang sudah dalam bentuk normal Greibach

    • Tentukan pengurutan simbol variabel, berdasarkan kondisi aturan produksi yang ada buatlah urutan sedemikian sehingga memudahkan untuk proses selanjutnya. Mulailah terlebih dahulu dari seimbol awal.

    §  Lakukan perubahan pada aturan produksi yang belum memenuhi ketentuan urutan tersebut dan bila perlu selama proses itu bisa dilakukan substitusi dan penghilangan rekursif kiri.

    • Lakukan substitusi mundur sedemikian rupa sehingga semua aturan produksi akan diawali dengan tepat sebuah simbol terminal. Proses substitusi mundur dimulai dari aturan produksi dengan urutan paling akhir.

    • Lakukan substitusi mundur juga pada aturan produksi baru yang muncul sebagai hasil penghilangan rekursif kiri.

    Contoh (simbol awal A) :

    A à BC
    B à CA | b
    C à AB | a
    Kita tentukan urutan simbol: A,B,C ( A<B<C )
    A à BC ( sudah memenuhi karena A<B)
    B à CA (sudah memenuhi karena B<C)
    C à AB (padahal C > A sehingga harus diubah)
    Pengubahan C à AB:
    C à AB => C à BCB => C à CACB | bCB
    Untuk C à CACB lakukan penghilangan rekursif kiri menjadi
    C à bCBZ1 | aZ1
    Z1 à ACB
    Z1 à ACBZ1

    Kita lihat seluruh hasil produksi dari variabel C, sudah dalam bentuk normal Greibach:
    C à bCBZ1 | aZ1 | bCB | a
    Setelah semua aturan produksi sudah memenuhi ketentuan urutan variabel, kita laukan substitusi mundur:
    B à CA => B à bCBZ1A | aZ1A | bCBA | aA
    A à BC => A à bCBZ1AC | aZ1AC | bCBAC | aAC | bC

    Selanjutnya lakukan pula substitusi pada aturan produksi dengan variabel baru yang terbentuk (pada contoh ini Z1) :
    §  Z1 à ACB => Z1 à bCBZ1ACCB | aZ1ACCB | bCBACCB | aACCB | bCCB
    §  Z1 à ACBZ1 => Z1 à bCBZ1ACCBZ1 | aZ1ACCBZ1 | bCBACCBZ1 | aACCBZ1 | bCCBZ1

    Hasil akhir aturan produksi dalam bentuk bentuk normal Greibach :
    A à bCBZ1AC | aZ1AC | bCBAC | aAC | bC |
    B à bCBZ1A | aZ1A | bCBA | aA | B
    C à bCBZ1 | aZ1 | bCB | a
    Z1 à bCBZ1ACCB | aZ1ACCB | bCBACCB | aACCB | bCCB
    Z1 à bCBZ1ACCBZ1 | aZ1ACCBZ1 | bCBACCBZ1 | aACCBZ1 | bCCBZ1

















    Sumber Pustaka :
    Teori Bahasa dan Otomata, Heru Cahya Rustamadji, Fakultas Teknik Industri Universitas Pembangunan Nasional, 2004.
    Computation Engineering : Applied Automata Theory and Logic, Gopalakrishnan, Ganesh, New York : Springer, 2006.
    Introduction to Automata Theory, Languages, and Computation, 2nd Edition, Hopcroft, John E. et al, New York : Addison-Wesley, 2001.


                   


                     





                   
                   

                   



                   


                   
    Tentang Penulis
    Adi S. Nugroho, lahir pada tanggal 25 Januari 1973, merupakan alumni dari STMIK (STI & K) Jakarta dan Universitas Krisnadwipayana. Menamatkan jenjang S1 pada bulan Pebruari 1996 dan menamatkan jenjang S2 pada bulan Maret 1999.
    Sebelum menekuni profesi sebagai dosen, pernah bekerja pada sebuah bank swasta nasional hingga mencapai posisi yang cukup tinggi, sebagai Management Information System (MIS) and Helpdesk Manager, juga pernah mengepalai Laboratorium Komputer di suatu SMK swasta nasional, dan terakhir adalah menduduki posisi sebagai HRD and GA Manager pada sebuah bengkel mobil Suzuki.







                   


                   


                   





























           






     

    1. MENGENAL OTOMATA
    1.1. Definisi Otomata

    Otomata adalah mesin abstrak yang dapat mengenali (recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu.

    Sedangkan arti Otomata menurut American Heritage Dictionary:

    1. a robot.

    2. one that behaves in an automatic or mechanical fashion.

    Sementara dalam dunia matematika, Otomata berkaitan dengan teori mesin abstrak, yaitu mesin sekuensial yang menerima input, dan mengeluarkan output, dalam bentuk diskrit. Contoh :

    Mesin Jaja / vending machine.

    Kunci kombinasi.

    Parser/compiler.

    1.2. Pengguna Pertama Istilah Otomata
    Istilah Otomata pertama kali tercantum dalam makalah yang berjudul “The Logical and General Theory of Automata”. Makalah ini ditulis oleh John Von Neumann dari The Institute for Advanced Study dan disajikan di Hixon Simposium pada tanggal 20 September 1948 di Pasadena, Kalifornia, Amerika Serikat.


    1.3. Buku Otomata Pertama
    Sebagai kelanjutan dari makalah tersebut, John Von Neumann menulis buku yang berjudul “Theory of Self-Reproducing Automata”. Buku ini diterbitkan oleh University of Illinois Press pada tahun 1966.

    1.4. Dasar-Dasar Otomata
    Secara garis besar, otomata mempunyai beberapa dasar, yaitu :
    Simbol adalah sebuah entitas abstrak (seperti halnya pengertian titik dalam geometri). Sebuah huruf atau sebuah angka adalah contoh simbol.

    String adalah deretan terbatas (finite) simbol-simbol. Sebagai contoh, jika a, b, dan c adalah tiga buah simbol maka abcb adalah sebuah string yang dibangun dari ketiga simbol tersebut.

    Jika w adalah sebuah string maka panjang string dinyatakan sebagai |w| dan didefinisikan sebagai cacahan (banyaknya) simbol yang menyusun string tersebut. Sebagai contoh, jika w = abcb maka |w| =  4.

    String hampa adalah sebuah string dengan nol buah simbol. String hampa dinyatakan dengan simbol ε (atau ^) sehingga |ε| = 0. String hampa dapat dipandang sebagai simbol hampa karena keduanya tersusun dari nol buah simbol.

    Alfabet adalah hinpunan hingga (finite set) simbol-simbol.

    Operasi Dasar String


    Diberikan dua string : x = abc, dan y = 123
    ·         Prefik string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling belakang dari string w tersebut.
    Contoh : abc, ab, a, dan e adalah semua Prefix(x)
    ·         ProperPrefix string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling belakang dari string w tersebut.
    Contoh : ab, a, dan e adalah semua ProperPrefix(x)
    ·         Postfix (atau Sufix) string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling depan dari string w tersebut.
    Contoh : abc, bc, c, dan e adalah semua Postfix(x)
    ·         ProperPostfix (atau PoperSufix) string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling depan dari string w tersebut.
    Contoh : bc, c, dan e adalah semua ProperPostfix(x)
    ·         Head string w adalah simbol paling depan dari string w.
    Contoh : a adalah Head(x)
    ·         Tail string w adalah string yang dihasilkan dari string w dengan menghilangkan simbol paling depan dari string w tersebut.
    Contoh : bc adalah Tail(x)
    ·         Substring string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling depan dan/atau simbol-simbol paling belakang dari string w tersebut.
    Contoh : abc, ab, bc, a, b, c, dan e adalah semua Substring(x)
    ·         ProperSubstring string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling depan dan/atau simbol-simbol paling belakang dari string w tersebut.
    Contoh : ab, bc, a, b, c, dan e adalah semua Substring(x)
    ·         Subsequence string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol dari string w tersebut.
    Contoh : abc, ab, bc, ac, a, b, c, dan e adalah semua Subsequence(x)
    ·         ProperSubsequence string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol dari string w tersebut.
    Contoh : ab, bc, ac, a, b, c, dan e adalah semua Subsequence(x)
    ·         Concatenation adalah penyambungan dua buah string. Operator concatenation adalah concate atau tanpa lambang apapun.
    Contoh : concate(xy) = xy = abc123
    ·         Alternation adalah pilihan satu di antara dua buah string. Operator alternation adalah alternate atau ½.
    Contoh : alternate(xy) = x½y = abc atau 123
    ·         Kleene Closure : x* = e½x½xx½xxx½… = e½x½x ½x ½

    ·         Positive Closure : x  = x½xx½xxx½… = x½x ½x ½

    Beberapa Sifat Operasi


    ·         Tidak selalu berlaku : x = Prefix(x)Postfix(x).

    ·         Selalu berlaku : x = Head(x)Tail(x).

    ·         Tidak selalu berlaku : Prefix(x) = Postfix(x) atau Prefix(x) ¹ Postfix(x).

    ·         Selalu berlaku : ProperPrefix(x) ¹ ProperPostfix(x).

    ·         Selalu berlaku : Head(x) ¹ Tail(x).

    ·         Setiap Prefix(x), ProperPrefix(x), Postfix(x), ProperPostfix(x), Head(x), dan Tail(x) adalah Substring(x), tetapi tidak sebaliknya.

    ·         Setiap Substring(x) adalah Subsequence(x), tetapi tidak sebaliknya.
    ·         Dua sifat aljabar concatenation :

    ¨      Operasi concatenation bersifat asosiatif : x(yz) = (xy)z.

    ¨      Elemen identitas operasi concatenation adalah e : ex = xe = x.

    ·         Tiga sifat aljabar alternation :

    ¨      Operasi alternation bersifat komutatif : x½y = y½x.

    ¨      Operasi alternation bersifat asosiatif : x½(y½z) = (x½y)½z.

    ¨      Elemen identitas operasi alternation adalah dirinya sendiri : x½x = x.

    ·         Sifat distributif concatenation terhadap alternation : x (y½z) = xy½xz.

    ·         Beberapa kesamaan :

    ¨      Kesamaan ke-1 : (x*)* = x*.

    ¨      Kesamaan ke-2 : e½x  = x ½e = x*.

    ¨      Kesamaan ke-3 : (x½y)* = e½x½y½xx½yy½xy½yx½… = semua string yang merupakan concatenation dari nol atau lebih x, y, atau keduanya.
















    2. FINITE STATE AUTOMATA

    2.1. Definisi

    Finite State Automata dinyatakan oleh 5 tuple  M = (Q , S , d , S , F ).

    Keterangan :

    Q = himpunan state.

    S = himpunan simbol input.

    d = fungsi transisi  d : Q ´ S.

    S = state awal / initial state ,   S Î Q.

    F = state akhir,  F Í Q.

    Contoh :
                    Q = {Genap, Ganjil}
                    S = {0,1}
                    S = Genap
                    F = {Ganjil }
    d
    0
    1

    Genap
    Genap
    Ganjil
         
    Ganjil
    Ganjil
    Genap

    atau
    d(Genap,0) = Genap
    d(Genap,1) = Ganjil
    d(Ganjil,0) = Ganjil
    d(Ganjil,1) = Genap


    Karakteristik dari Finite State Automata sebagai berikut :
    ¨           Model matematika yang dapat menerima input dan mengeluarkan output.

    ¨           Memiliki state yang berhingga banyaknya dan dapat berpindah dari satu state ke state lainnya berdasar input dan fungsi transisi.

    ¨           Tidak memiliki tempat penyimpanan/memori, hanya bisa mengingat state terkini.

    ¨           Mekanisme kerja dapat diaplikasikan pada : elevator, teks editor, analisa leksikal, cek pariti.

    Contoh Cek Pariti ganjil

    Misal :
     1101
    Genap 1 Ganjil 1 Genap 0 Genap 1 Ganjil di terima  oleh mesin.

    Misal :

     

    1100

    Genap 1 Ganjil 1 Genap 0 Genap 0 Genap di tolak oleh mesin.


    2.2. Jenis
    Finite State Automata terdiri atas :
    Deterministic Finite Automata (DFA) : dari suatu state ada tepat satu state berikutnya untuk setiap simbol masukan yang diterima,
    DFA terdiri atas :
    §  Himpunan keadaan (state),
    §  Alfabet atau himpunan huruf,
    §  Satu keadaan awal,
    §  Himpunan keadaan akhir, dan
    §  Fungsi transisi.
    Non-deterministic Finite Automata (NFA) : dari suatu state ada 0, 1 atau lebih state berikutnya untuk setiap simbol masukan yang diterima
    NFA terdiri atas :
    §  Himpunan keadaan (state),
    §  Alfabet atau himpunan huruf,
    §  Satu keadaan awal,
    §  Himpunan keadaan akhir, dan
    §  Relasi transisi.

    Deterministic Finite Automata


    ¨           Contoh :  pengujian pariti ganjil.

    ¨           Contoh lain : pengujian untuk menerima bit string dengan banyaknya 0 genap, serta banyaknya 1 genap.

    ¨           0011 : diterima.
    .
    ¨           10010 : ditolak, karena banyaknya 0 ganjil.

    ¨           Diagram transisi-nya :
    ¨           DFA  sebagai berikut :

                Q = {q0 , q1 , q2 , q3 }
                S = {0,1}
                S = q0
                F = { q0}
    fungsi transisi
    d
    0
    1
    q0
    q2
    q1
    q1
    q3
    q0
    q2
    q0
    q3
    q3
    q1
    q2
       d( q0,011) =  d( q2,11)  = d( q3,1) =  q2                                     Ditolak.
       d( q0,1010) =  d( q1,010)  = d( q3,10)  = d( q2,0) =  q0         Diterima.

    ¨           Contoh lain DFA : Variabel dalam bahasa pascal diawali oleh huruf (besar/kecil), dan diikuti dengan huruf atau angka.
















    ¨           Contoh DFA lainnya :


     

    Nondeterministic Finite Automata


    *  Perbedaan dengan NFA: fungsi transisi dapat memiliki 0 atau lebih fungsi transisi.


    ¨           G = ({q0 , q1 , q2 , q3, q4 }, {0,1}, d ,  q0 , { q2 , q4}}

    d
    0
    1
    q0
    { q0,q3}
    {q0,q1}
    q1
    e
    {q2}
    q2
    {q2}
    {q2}
    q3
    {q4}
    e
    q4
    {q4}
    {q4}
    ¨           String diterima NFA bila terdapat suatu urutan transisi berdasar input, dari state awal ke state akhir.

    ¨           harus mencoba semua kemungkinan.

    ¨           Contoh : string 01001
    * Dua buah FSA disebut ekuivalen apabila kedua FSA tersebut menerima bahasa yang sama
    Contoh : FSA yang menerima bahasa {an | n³0 }

    *  Dua buah state dari FSA disebut indistinguishable  (tidak dapat dibedakan) apabila :
    d(q,w)ÎF sedangkan d(p,w)ÏF dan
    d(q,w) ÏF sedangkan d(p,w) ÎF untuk semua w Î S*
    *  Dua buah state dari FSA disebut distinguishable  (dapat dibedakan) bila terdapat w Î S* sedemikian hingga:
    d(q,w)ÎF sedangkan d(p,w)ÏF dan
    d(q,w) ÏF sedangkan d(p,w) ÎF untuk semua w Î S*
    Prosedur menentukan pasangan status indistinguishable sebagai berikut :
    1.      Hapus semua state yang tak dapat dicapai dari state awal.

    2.      Catat semua pasangan state (p,q) yang distinguishable, yaitu {(p,q) | p Î F Ù q Ï F}.

    3.      Untuk setiap pasangan (p,q) sisanya, untuk setiap aÎ S,  tentukan d(p,a) dan d(q,a).





    Contoh :
    1.      Hapus state yang tidak tercapai -> tidak ada.

    2.      Pasangan distinguishable (q0,q4), (q1,q4), (q2,q4), (q3,q4).

    3.      Pasangan sisanya (q0,q1), (q0,q2), (q0,q3), (q1,q2) (q1,q3) (q2,q3) .

    pasangan
    state 1
    state 2
    Hasil
    0
    1
    0
    1
    (q0,q1)
    q1
    q3
    q2
    q4
    distinguishable
    (q0,q2)
    q1
    q3
    q1
    q4
    distinguishable
    (q1,q2)
    q2
    q4
    q1
    q4
    indistinguishable
    (q0,q3)
    q1
    q3
    q2
    q4
    distinguishable
    (q1,q3)
    q2
    q4
    q2
    q4
    indistinguishable
    (q2,q3)
    q1
    q4
    q2
    q4
    indistinguishable
    Catatan : jumlah pasangan seluruhnya :
    Prosedur Reduksi DFA sebagai berikut :
    1.      Tentukan pasangan status indistinguishable.

    2.      Gabungkan setiap group indistinguishable state ke dalam satu state dengan relasi pembentukan group secara berantai : Jika p dan q indistingishable dan jika q dan r indistinguishable maka p dan r indistinguishable, dan p,q serta r indistinguishable semua berada dalam satu group.

    3.      Sesuaikan transisi dari dan ke state-state gabungan.

    Contoh
    1.      pasangan status indistinguishable (q1,q2), (q1,q3)  dan (q2,q3).

    2.      q1,q2,q3 ketiganya dapat digabung dalam satu state q123.

    3.      Menyesuaikan transisi, sehingga DFA menjadi















    3. Tata Bahasa Bebas Konteks

     

    3.1. Gambaran Bahasa Bebas Konteks

     

    Konsep Dasar


    • Anggota alfabet dinamakan simbol terminal.

    • Kalimat adalah deretan hingga simbol-simbol terminal.

    • Bahasa adalah himpunan kalimat-kalimat. Anggota bahasa bisa tak hingga kalimat.

    • Simbol-simbol berikut adalah simbol terminal :

    ü  huruf kecil, misalnya : a, b, c, 0, 1, …

    ü  simbol operator, misalnya : +, -, dan ´

    ü  simbol tanda baca, misalnya : (,  ),  dan ;

    ü  string yang tercetak tebal, misalnya : if, then, dan else.

    • Simbol-simbol berikut adalah simbol non terminal /Variabel :

    ü  huruf besar, misalnya : A, B, C

    ü  huruf S sebagai simbol awal

    ü  string yang tercetak miring, misalnya : expr .

    • Huruf yunani melambangkan string yang tersusun atas simbol-simbol terminal atau simbol-simbol non terminal atau campuran keduanya, misalnya : a, b, dan g.

    • Sebuah produksi dilambangkan sebagai a ® b, artinya : dalam sebuah derivasi dapat dilakukan penggantian simbol a dengan simbol b.

    • Derivasi adalah proses pembentukan sebuah kalimat atau sentensial. Sebuah derivasi dilambangkan sebagai : a Þ b.

    • Sentensial adalah string yang tersusun atas simbol-simbol terminal atau simbol-simbol non terminal atau campuran keduanya.

    • Kalimat adalah string yang tersusun atas simbol-simbol terminal. Kalimat adalah merupakan sentensial, sebaliknya belum tentu..

    Deskripsi bahasa alami :


     <kalimat>                   ® <subjek> <predikat>

    <subjek>                                 ® <kata benda>

    <predikat>                  ® <kata kerja>

    <kata benda>              ® kucing

    <kata kerja>                ® berlari

    <kata kerja>                ® menyapu


    Contoh  :        

     

    ·         kucing berlari.

                     

    ·         kucing menyapu    (sintaks yes, semantik no).


    Dalam tatabahasa bebas konteks :


    ·         Ruas kiri dari aturan produksi terdiri dari satu simbol non terminal.

    ·         Ruas kanan dapat berupa string yang dibentuk dari simbol terminal dan non  terminal.

    Contoh
    S ®aSb | e
    Kalimat-kalimat yang dibangkitkan dari aturan produksi itu adalah e,ab,aabb,aaabbb,... , anbn

    Contoh
    A ®0A0
    A ®1A1
    A®a
    Kalimat-kalimat yang dibangkitkan dari aturan produksi itu adalah a,01a10, 1001a1001 , 110a011 babR

    Contoh :

    S ® aSb | SS |e

    Bahasa yang dihasilkan oleh tatabahasa dengan aturan produksi di atas adalah :

    L = {w Î (a + b)* |na(w) =nb(w) }

    3.2. Leftmost dan Rightmost Derivation

    Suatu penguraian /penurunan dikatakan leftmost derivation bila setiap tahapan penurunan variabel / non terminal terkiri yang diuraikan. Apabila setiap tahapan penurunan variabel / non terminal paling kanan yang diuraikan disebut rightmost derivation



    Contoh 1 :

    G=({A,B,S}, {a,b},S,P} dengan aturan produksi P :

                S ® AB
                A® aaA | l
    B®Bb | l

    Menspesifikasikan bahasa :

                L(G) = {a2nbm | n³0 , m³0}

    Leftmost derivation untuk menghasilkan string aab

     S Þ AB Þ aaAB Þ aaB Þ aaBb  Þ aab

    Righmost derivation untuk menghasilkan string aab

                S  Þ AB  Þ ABb  Þ aaABb  ÞaaAb  Þaab

    Contoh 2 :

    G=({A,B,S}, {a,b},S,P} dengan aturan produksi P :

                S ® aAB
                A® bBb
    B® A | l

    Leftmost derivation untuk menghasilkan string abbbb

        S Þ aAB Þ abBbB Þ abAbB Þ abbBbbB
           Þ abbbbB Þ abbbb

    Righmost derivation untuk menghasilkan string abbbb

        S  Þ aAB Þ aA Þ abBb Þ abAb Þ abbBbb Þ abbbb

    3.3. Pohon Urai

    Untuk menampilkan penguraian, dapat dilakukan dengan membentuk pohon urai (sayangnya, urutan penguraian tidak terlihat).








    Contoh  :


    3.4. Parsing dan Keanggotaan

    Untuk menentukan apakah string w berada di L(G), dengan cara secara sistematis membangun semua kemungkinan penurunan, dan mencocokkan hasilnya apakah ada yang sama dengan string w.  (disebut exhaustive search parsing)

    Contoh :

    Menentukan apakah string ab berada pada bahasa yang dibentuk oleh grammar dengan aturan produksi S ® SS | aSb | bSa | l.

    Untuk penguraian pertama :

    1. S Þ SS
    2. S Þ aSb
    3. S Þ bSa
    4. S Þ l

    Penguraian nomor 3 dan 4 tidak perlu dilanjutkan. Penguraian 1 dan Penguraian 2 terbentuk sebagai berikut :

    1a. S Þ SS Þ SSS                             2a. S Þ aSb Þ aSSb
    1b. S Þ SS Þ aSbS                           2b. S Þ aSb Þ aaSbb
    1c. S Þ SS Þ bSaS                           2c. S Þ aSb Þ abSab
    1d. S Þ SS Þ S                                 2d. S Þ aSb Þ ab

    3.5. Ambiguitas pada Tatabahasa dan Bahasa

    Tatabahasa bebas konteks G disebut ambigu jika terdapat beberapa w Î L(G) yang mempunyai paling sedikit dua buah pohon penurunan

    Contoh :

    Tatabahasa dengan aturan produksi S ® SS | aSb | l.

    string aabb mempunyai 2 pohon penurunan :
     

    3.6. Pumping Lemma untuk bahasa bebas konteks

    ¨        Jika suatu rangkaian simbol / string yang cukup panjang yang merupakan sebuah bahasa bebas konteks, maka kita dapat menemukan dua substring yang jaraknya berdekatan yang jika dipompa, string baru yang diperoleh merupakan bahasa bebas konteks juga.

    ¨        Secara formal, lemma di atas dinyatakan dengan


    ¨        Syarat “ kedua lokasi berdekatan” dinyatakan dengan kondisi |vwx| £ n.

    ¨        Jika salah satu v atau x diambil sebagai string kosong, maka lemma diatas berubah menjadi lemma untuk bahasa reguler

    Contoh :

    Tatabahasa dengan aturan produksi

    S  ®uAy
    A ® vAx
    A ® w


    maka aturan derivasinya sebagai berikut :

    S Þ uAy Þ uwy
    S Þ uAy Þ uvAxy Þuvwxy
    S Þ uAy Þ uvAxy Þ uvvAxxy Þuvvwxxy

    sehingga untuk setiap i ³0 , uviwxiy Î L.

     3.7. Sifat sifat tertutup bahasa bebas konteks

    ¨        Gabungan  dua CFL merupakan CFL juga.

    Jika diketahui dua buah CFG G1= (N1,T1,S1,P1) dan G2=(N2,T2,S2,P2) yang menghasilkan bahasa L1 dan L2 ,  maka CFG L1 È L2 dapat dibentuk dengan cara :
    1.      Menggabungkan kedua himpunan dan menambahkan satu simbol variabel baru S

    2.      Menggabungkan kedua himpunan simbol terminal

    3.      Menggabungkan kedua himpunan aturan produksi dan menambahkan satu aturan produksi baru

    S ® S1|S2 yang digunakan untuk memilih salah satu simbol awal S1 atau S2 dari simbol awal baru S
    G3 = (N1ÈN2­È{S},T1ÈT2 ,S,P1ÈP2 È{S®S1|S2}}
    ¨        Penyambungan dua CFL merupakan CFL juga.

    Jika diketahui dua buah CFG G1= (N1,T1,S1,P1) dan G2=(N2,T2,S2,P2) yang menghasilkan bahasa L1 dan L2 ,  maka bahasa L1L2 dapat dibentuk oleh :
    G4 = (N1ÈN2­È{S},T1ÈT2 ,S,P1ÈP2 È{S®S1S2}}
    ¨        Klosure Kleene dari CFL adalah CFL juga.

    Klosure Kleene dari tatabahasa G=(N,T,S1,P) adalah
    G5 = (N È {S} , T , S , P È {S ® S1S | e } )
    ¨        Bahasa bebas konteks tertutup terhadap substitusi

    Contoh :
    La = {0 n1n | n ³1 } dan Lb = { wwR | w Î (0+2)* }
    dihasilkan oleh tatabahasa Ga dengan aturan produksi
          Sa ® 0Sa1 | 01 serta tatabahasa G2 dengan aturan produksi Sb ® 0Sb0 | 2Sb2 | e.

    Didefinisikan tatabahasa G dengan aturan produksi S ® aSbS | bSaS | e


    Jika f adalah substitusi f(a)= La dan f(b) = Lb maka  f(L) adalah bahasa yang dihasilkan oleh tatabahasa dengan aturan produksi :
          S ® SaSSbS | SbSSaS | e
          Sa ® 0Sa1 | 01

          Sb ® 0Sb0 | 2Sb2 | e

    Tatabahasa Bebas Konteks dan Bahasa Pemrograman


    ¨        Tatabahasa bebas konteks digunakan untuk mendefinisikan sintaks bahasa pemrograman.

    ¨        Menggunakan notasi BNF (Backus-Naur Form).

    ¨        Variabel / non terminal :  <...> .

    ¨        Terminal : tanpa tanda.

    ¨        ¬ diganti dengan ::=

    ¨        Contoh :

    Statement  if then else

    < if_statement> ::= if <expression>
    <then_clause>
    <else_clause>










    4. PENYEDERHANAAN TATA BAHASA BEBAS KONTEKS

    4.1. Tujuan
    Melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tidak perlu atau aturan produksi yang tidak berarti.
    Contoh 1 :
    S à AB | a
    Aàa
    ¨           Aturan produksi S à AB tidak berarti karena B tidak memiliki penurunan

    Contoh 2 :
                    SàA
    AàB
    BàC
    CàD
    D à a | A
    ¨           Memiliki kelemahan terlalu panjang jalannya padahal berujung pada S à a,

    ¨           produksi  D à A juga menyebabkan kerumitan.

    Cara Penyederhanaan:
    1. Penghilangan produksi useless ( tidak berguna ).

    1. Penghilangan produksi unit.

    1. Penghilangan produksi ε .

    4.2. Penghilangan Produksi Useless
    Di sini produksi useless didefinisikan sebagai :
    ·                     Produksi yang memuat simbol variabel yang tidak memiliki penurunan yang akan menghasilkan terminal-terminal seluruhnya.

    ·                     Produksi yang tidak akan pernah dicapai dengan penurunan apapun dari simbol awal, sehingga produksi itu redundan ( berlebih ).

    Contoh :
    S à aSa | Abd | Bde
    A à Ada
    Bà BBB | a
    Maka
    1)      Simbol variabel A tidak memiliki penurunan yang menuju terminal, sehingga bisa dihilangkan

    2)      Konsekuensi no (1), aturan produksi S à Abd tidak memiliki penurunan

    Penyederhanaan menjadi:
    SàaSa | Bde
    Bà BBB | a
    Contoh :
    Sà Aa | B
    Aàab | D
    Bà b | E
    Cà bb
    Eà aEa
    Maka :
    §  Aturan produksi A à D, simbol variabel D tidak memiliki penurunan.

    §  Aturan produksi C à bb, Penurunan dari simbol S, dengan jalan manapun tidak akan pernah mencapai C.

    §  Simbol variabel E tidak memiliki aturan produksi yang menuju terminal.           

    §  Konsekuensi no (3) Aturan produksi B à E, simbol variabel E tidak memiliki penurunan.

    §  Produksi yang useless:
    A à D
    C à bb
    E à aEa
    B à E
    Penyederhanaannya menjadi:
    S à Aa | B
    A à ab
    B à b
    Contoh :
                    S à aAb | cEB
    A à dBE | eeC
    B à ff
    C à ae
    D à h
    Analisa :
    1)      Aturan produksi S à cEB, A à dBE dapat dihilangkan ( E tidak memiliki penurunan).

    2)      Aturan produksi D à h, redundan

    Sisa aturan produksi
    S à aAb
    A à eeC
    B à ff
    C à ae
    Analisis lagi
                    B à ff juga redundan,
    Hasil penyederhanaan menjadi:
    S à aAb
    A à eeC
    C à ae
    Contoh lain lagi :
    S à aB
    A à bcD | dAC
    B à e | Ab
    C à bCb | adF | ab
    F à cFB
    Analisa :
    1)      Aturan produksi A à bcD, variabel D tidak memiliki penurunan.

    2)       Konsekuensi no (1), simbol variabel A tidak memiliki penurunan yang menuju terminal (tinggal A à dAC).

    3)      Konsekuensi no (2),  B à Ab tidak memiliki penurunan.

    4)      Simbol variabel F tidak memiliki penurunan yang menuju terminal.

    5)      Konsekuensi no (4), C à adF tidak memiliki penurunan

    Setelah disederhanakan menjadi:
    S à aB
    B à e
    C à bCb | ab
    Contoh  :
    S à aBD
    B à cD | Ab
    D à ef
    A à Ed
    F à dc
    Analisa :
    1)      Aturan produksi A à Ed, E tidak memiliki penurunan.

    2)      Aturan produksi F à dc, redundan.

    Sisa aturan produksi:
    S à aBD
    B à cD | Ab
    D à ef
    Analisa lagi
                    B à Ab, A tidak memiliki penurunan.
    Hasil penyederhanaan:
    S à aBD
    B à cD
    D à ef
    Contoh lagi:
    S à Abc | ab
    A à AAA | ε
    Aturan produksi setelah disederhanakan:
    S à Abc | ab
    A à AAA | ε
    Ingat A à ε juga harus diperhitungkan

    PRINSIP


    Setiap kali melakukan penyederhanaan diperiksa lagi aturan produksi yang tersisa, apakah semua produksi yang useless sudah hilang.
    Penghilangan Produksi Unit
    ¨           Produksi dimana ruas kiri dan kanan aturan produksi hanya berupa satu simbol variabel, misalkan: A à B, C à D.

    ¨           Keberadaannya membuat tata bahasa memiliki kerumitan yang tak perlu.

    ¨           Penyederhanaan dilakukan dengan melakukan penggantian aturan produksi unit.

    Contoh:
    S à Sb
    S à C
    C à D
    C à ef
    D à dd
    Dilakukan penggantian berturutan mulai dari aturan produksi yang paling dekat menuju ke penurunan terminal-terminal (‘=>’ dibaca ‘menjadi’):
    ·                     C à D => C à dd

    ·                     S à C => S à dd | ef

    Sehingga aturan produksi setelah penyederhanaan:
    S à Sb
    S à dd | ef
    C à dd
    C à ef
    D à dd
    Contoh :
    S à A
    S à Aa
    A à B
    B à C
    B à b
    C à D
    C à ab
    D à b
    Penggantian yang dilakukan :
    ·                     C à D => C à b

    ·                     B à C => B à b | ab, karena B à b sudah ada, maka cukup dituliskan B à ab

    ·                     A à B => A à ab | b

    ·                     S à A => ab | b

    Sehingga aturan produksi setelah penyederhanaan:
    S à ab | b
    S à Aa
    A à ab | b
    B à ab
    B à b
    C à b
    C à ab
    D à b
    Contoh :
    S à Cba | D
    A à bbC
    B à Sc | ddd
    C à eAn | f | C
    D à E | SABC
    E à gh
    Penggantian yang dilakukan:
    ·                     D à E menjadi D à gh

    ·                     C à C , kita hapus

    ·                     S à D menjadi S à gh | SABC

    Sehingga aturan produksi setelah penyederhanaan:
    S à Cba | gh | SABC
    A à bbC
    B à Sc | ddd
    C à eA | f
    D à gh | SABC
    E à gh
    Penghilangan Produksi ε
                    Produksi ε adalah produksi dalam bentuk
    α à ε
    atau bisa dianggap sebagai produksi kosong ( empty ). Penghilangan produksi ε dilakukan dengan melakukan penggantian produksi yang memuat variabel yang bisa menuju produksi ε, atau biasa disebut nullable. Prinsip penggantiannya bisa dilihat kasus berikut :
    S à bcAd
    A à ε
    A nullable serta A à ε satu-satunya produksi dari A, maka variabel A bisa ditiadakan, hasil penyederhanaan tata bahasa bebas konteks menjadi:
    S à bcd
    Tetapi bila kasusnya:
    S à bcAd
    A à bd | ε
    A nullable, tapi A à ε bukan satu-satunya produksi dari A, maka hasil penyederhanaan:
    S à bcAd | bcd
    A à bd
    Contoh lagi, terdapat tata bahasa bebas konteks:
    S à Ab | Cd
    A à d
    C à ε
    Variabel yang nullable  adalah variabel C. Karena penurunan C à ε merupakan penurunan satu-satunya dari C, maka kita ganti S à Cd menjadi S à d. Kemudian produksi C à ε kita hapus.
    Setelah penyederhanaan menjadi :
    S à Ab | d
    A à d
    Contoh :
    S à dA | Bd
    A à bc
    A à ε
    B à c
    Variabel yang nullable adalah variabel A. A à ε bukan penurunan satu-satunya dari A ( terdapat A à bc ), maka kita ganti S à dA menjadi S à dA | d.A à ε kita hapus.
    Setelah penyederhanaan :
    S à dA | d | Bd
    A à bc
    B à c
    Contoh tata bahasa bebas konteks:
    S à AaCD
    A à CD | AB
    B à b | ε
    C à d | ε
    D à ε
    Variabel yang nullable adalah variabel B, C, D. Kemudian dari  A à CD, maka variabel A juga nullable ( A à ε ). Karena D hanya memilki penurunan D à ε, maka kita sederhanakan dulu:
    S à AaCD => S à AaC
    A à CD => A à C
    D à ε kita hapus

    Selanjutnya kita lihat variabel B dan C memiliki penurunan ε, meskipun bukan satu-satunya penurunan, maka dilakukan penggantian:
    ·                     A à AB => A à AB | A | B
    ·                     S à AaC => S à AaC | aC | Aa | a
    ·                     B à ε dan C à ε kita hapus
    Setelah penyederhanaan:
    S à AaC | aC | Aa | a
    A à C | AB | A | B
    B à b
    C à ε
    Variabel yang nullable adalah A, B, C. Dari S à AB, maka S juga nullable. Kita lakukan penggantian:
    A à aCa => A à aa
    B à bA => B à bA | b
    B à BB => B à BB | B
    A à abB => A à abB | ab
    S à AB => S à AB | A | B | ε
    C à ε, B à ε, A à ε dihapus

    * Perhatikan untuk penggantian S à AB kita tetap mempertahankan S à ε, karena S merupakan simbol awal. Ini merupakan satu-satunya perkecualian produksi ε yang tidak dihapus, yaitu produksi ε yang dihasilkan oleh simbol awal.
    Hasil akhir dari penyederhanaan:
    S à AB | A | B | ε
    A à abB | ab | aa
    B à bA | b | BB | B
    Contoh :
    Tata bahasa bebas konteks :
    S à aAb
    A à aAb | ε
    Hasil penyederhanaan :
    S à aAb | ab
    A à aAb | ab
    Contoh :
    Tata bahasa bebas konteks :
    S à ABaC
    A à BC
    B à b | ε
    C à D | ε
    D à d

    Hasil penyederhanaan:
    S à ABaC | BaC | AaC | ABa | aC | Aa | Ba | a
    A à B | C | BC
    B à b
    C à D
    D à d
    Prakteknya ketiga penyederhanaan tersebut  dilakukan bersama pada suatu tata bahasa bebas konteks, yang nantinya menyiapkan tata bahasa bebas konteks tersebut untuk diubah kedalam suatu bentuk normal Chomsky.
    Urutan penghapusan aturan produksi :
    1)      Hilangkan produksi ε

    2)      Hilangkan produksi unit

    3)      Hilangkan produksi useless

    Contoh :
    S à AA | C | bd
    A à Bb | ε
    B à AB | d
    C à de
    Hilangkan produksi ε, sehingga menjadi:
    S à A | AA | C | bd
    A à Bb
    B à B | AB | d
    C à de
    Selanjutnya penghilangan produksi unit menjadi:
    S à Bb | AA | de | bd
    A à Bb
    B à AB | d
    C à de

    Penghilangan produksi unit bisa menghasilkan produksi useless.  Terakhir dilakukan penghilangan produksi useless:
    S à Bb | AA | de | bd
    A à Bb
    B à AB | d
    Hasil akhir aturan produksi tidak lagi memiliki produksi ε, produksi unit, maupun produksi useless.




    5. BENTUK NORMAL CHOMSKY

    5.1. Definisi Bentuk Normal Chomsky
    Bentuk normal Chomsky / Chomsky Normal Form  (CNF) merupakan salah satu bentuk normal yang sangat berguna untuk tata bahasa bebas konteks ( CFG ). Bentuk normal Chomsky dapat dibuat dari sebuah tata bahasa bebas konteks yang telah mengalami penyederhanaan yaitu penghilangan produksi useless, unit, dan ε. Dengan kata lain, suatu tata bahasa bebas konteks dapat dibuat menjadi bentuk normal Chomsky dengan syarat tata bahasa bebas konteks tersebut:
    ·                     Tidak memiliki produksi useless

    ·                     Tidak memiliki produksi unit

    ·                     Tidak memiliki produksi ε

    Aturan produksi dalam  bentuk normal Chomsky ruas kanannya tepat berupa sebuah terminal atau dua variabel. Misal :
    A à BC
    A à b
    B à a
    C à BA | d
    Pembentukan Bentuk Normal Chomsky
    Langkah-langkah pembentukan  bentuk normal Chomsky  secara umum sebagai berikut:
    ·                     Biarkan aturan produksi yang sudah dalam  bentuk normal Chomsky .

    ·                     Lakukan penggantian aturan produksi yang ruas kanannya memuat simbol terminal dan panjang ruas kanan > 1.

    ·                     Lakukan penggantian aturan produksi yang ruas kanannya memuat > 2 simbol variabel.

    ·                     Penggantian-penggantian tersebut bisa dilakukan berkali-kali sampai akhirnya semua aturan produksi dalam  bentuk normal Chomsky  .

    ·                     Selama dilakukan penggantian, kemungkinan kita akan memperoleh aturan-aturan produksi baru, dan juga memunculkan simbol-simbol variabel baru


    Contoh, tata bahasa bebas konteks ( kita anggap tata bahasa bebas konteks pada bab ini sudah mengalami penyederhanaan ) :

    S à bA | aB
    A à bAA | aS | a
    B à aBB | bS | b

    Aturan produksi yang sudah dalam  bentuk normal Chomsky :

    A à a
    B à b

    Dilakukan penggantian aturan produksi yang belum bentuk normal Chomsky (‘=>’ bisa dibaca berubah menjadi) :

    S à bA => S à P1A
    S à aB => S à P1B
    A à bAA => S à P1AA => A à P1P3
    A à aS => A à P2S
    B à aBB => B à P2BB => B à P2P4
    B à bS => B à P1S
    Terbentuk aturan produksi dan simbol variabel baru :
    P1 à b
    P2 à a
    P3 à AA
    P4 à BB
    Hasil akhir aturan produksi dalam bentuk normal Chomsky :

    A à a
    B à b
    S à P1A
    S à P2B
    A à P1P3
    A à P2S
    B à P2P4
    B à P1S
    P1 à b
    P2 à a
    P3 à AA
    P4 à BB

    Contoh, tata bahasa bebas konteks:

    S à aB | CA
    A à a | bc
    B à BC | Ab
    C à aB | b
    Aturan produksi yang sudah dalam bentuk normal Chomsky :

    S à CA
    A à a
    B à BC
    C à b

    Penggantian aturan produksi yang belum dalam bentuk normal Chomsky :

    S à aB => S à P1B
    A à bc => S à P2P3
    B à Ab => B à A P2
    C à aB => C à P1B

    Terbentuk aturan produksi dan simbol variabel baru :

    P1 à a
    P2 à b
    P3 à c

    Hasil akhir aturan produksi dalam  bentuk normal Chomsky :

    S à CA
    A à a
    B à BC
    C à b
    S à P1B
    S à P2P3
    B à A P2
    C à P1B
    P1 à a
    P2 à b
    P3 à c
    Contoh :
    Tata bahasa bebas konteks  :
    S à aAB | ch | CD
    A à dbE | eEC
    B à ff | DD
    C à ADB | aS
    D à i
    E à jD
    Aturan produksi yang sudah dalam bentuk normal Chomsky :
    S à CD
    B à DD
    D à  i


    Penggantian aturan produksi:
    S à aAB => S à P1P2
    S à ch => S à P3P4
    A à dbE => A à P5P6
    A à eEC => A à P8P9
    B à ff => B à P10P10
    C à ADB => C à AP11
    C à aS => C à P1S
    E à jD => E à P12D
    Terbentuk aturan produksi baru:
    P1 à a
    P2 à AB
    P3 à c
    P4 à h
    P5 à d
    P6 à P7E
    P7 à b
    P8 à e
    P9 à EC
    P10 à f
    P11 à DB
    P12 à j
    Hasil akhir dalam bentuk normal Chomsky:
    S à CD
    B à DD
    D à i
    S à P1P2
    S à P3P4
    A à P5P6
    A à P8P9
    B à P10P10
    C à AP11
    C à P1S
    E à P12D
    P1 à a
    P2 à AB
    P3 à c
    P4 à h
    P5 à d
    P6 à P7E
    P7 à b
    P8 à e
    P9 à EC
    P10 à f
    P11 à DB
    P12 à j
    4.2. Algoritma CYK untuk Tata Bahasa Bebas Konteks
    Algoritma CYK merupakan algoritma parsing dan keanggotaan ( membership) untuk tata bahasa bebas konteks. Algortima ini diciptakan oleh J. Cocke, DH. Younger, dan T. Kasami. Syarat untuk penggunaan algortima ini adalah tata bahasa harus berada dalam  bentuk normal Chomsky . Obyektivitas dari algortima ini untuk menunjukkan apakah suatu  string dapat diperoleh dari suatu tata bahasa.
    Algoritma CYK sebagai berikut:
    begin
    1)  for i:= 1 to n do
    2)  Vi1 := {A| A à a aturan produksi dimana simbol ke- i adalah a };
    3)  for j:= 2 to n do
    4)      for i:= 1 to (n-j+1) do
    begin
    5)             Vij:=Ø;
    6)             for k:=1 to (j – 1) do
    7)                  Vij:= Vij υ ( A | A à BC adalah suatu produksi, dimana B di Vik dan C di Vi+k,j-k }
    end
    end
    Penjelasan:
    ·                     n = panjang untai yang akan diperiksa, missal : untuk untai ‘ada’, n = | ada | =3

    ·                     i  akan menyatakan kolom ke-

    ·                     j  akan menyatakan baris ke-

    ·                     tahapan no (1) dan (2) untuk mengisi table baris pertama kolom 1 – n

    ·                      no (3), interasi dari baris ke- 2 sampai n

    ·                     no (4), interasi untuk mengisi kolom 1 sampai ( n – baris + 1) pada suatu baris.

    ·                     no (5) inisialisasi  Vij dengan Ø

    ·                      no (6) dan no (7), interasi untuk memeriksa mana saja yang menjadi anggota Vij


                   



                   






    6. PENGHILANGAN REKURSIF KIRI

    6.1. Aturan Produksi Rekursif
                   
    Aturan  Produksi yang rekursif memilki ruas kanan (hasil produksi) yang memuat simbol variabel pada ruas kiri. Sebuah aturan produksi dalam bentuk : A à βA merupakan aturan produksi yang rekursif kanan.

    Keterangan :

    β=(VÈT)* atau kumpulan simbol variabel dan terminal
    Contoh aturan produksi yang rekursif kanan:
    S à dS
    B à adB
    Produksi dalam bentuk:
    A à
    Merupakan aturan produksi yang rekursif kiri,
    Contoh :
    S è Sd
    B à Bad
    Produksi yang rekursif kanan menyebabkan pohon penurunan tumbuh ke kanan, sebaliknya Produksi yang rekursif kiri menyebabkan pohon penurunan tumbuh ke kiri.
    Dalam banyak penerapan tata bahasa, rekursif kiri tak diinginkan. Untuk menghindari penurunan yang bisa mengakibatkan loop kita perlu menghilangkan sifat rekursif kiri dari aturan produksi. Penghilangan rekursif kiri disini memungkinkan suatu tata bahasa bebas konteks nantinya diubah ke dalam bentuk normal Greibach.
    6.2. Tahapan Penghilangan Rekursif Kiri
    Langkah-langkah penghilangan rekursif kiri sebagai berikut :
    §     Pisahkan aturan produksi yang rekursif kiri dan yang tidak, missal :



    Aturan produksi yang rekursif kiri :
    A à1 | Aα2 | Aα3 | ....... Aαn  
    Aturan produksi yang tidak rekursif kiri (termasuk produksi ε) :
    A à β1 | β2 | β3 | ........ βm
         
    §  Dari situ kita bisa tentukan α1, α2, .... αn,  dan β1, β2, .... βm  dari setiap aturan produksi yang memiliki simbol ruas kiri yang sama.

    §  Lakukan penggantian aturan produksi yang rekursif kiri, menjadi sebagai berikut:

    ü  A à β1Z | β2Z | .... βmZ
    ü  Z à  α1 | α2  | α3 | .... αn
    ü  Z à α1Z | α2Z | α3Z | .... αnZ

    Penggantian diatas dilakukan untuk setiap aturan produksi dengan simbol ruas kiri yang sama. Bisa muncul simbol variabel baru Z1, Z2 dan seterusnya, sesuai banyaknya variabel yang menghasilkan produksi yang rekursif kiri.
    §  Hasil akhir berupa aturan produksi pengganti ditambah dengan aturan produksi semula yang tidak rekursif kiri.

    Contoh :
    Ttata bahasa bebas konteks :
    S à Sab | aSc |dd | ff | Sbd

    Pertama-tama kita lakukan pemisahan aturan produksi
    Aturan produksi yang rekursif kiri : S à Sab | Sbd
    Dari situ kita tentukan :
    Untuk simbol ruas kiri sebagai berikut S : α1 = ab, α2 = bd
    Aturan produksi yang tidak rekursif kiri : S à aSc | dd | ff
    Dari situ kita dapatkan:
    Untuk simbol ruas kiri sebagai berikut : S : β1 = aSc, β2 = dd, β3 = ff
    Kita lakukan penggantian aturan produksi yang rekursif kiri:
    Untuk yang memiliki simbol ruas kiri S:
    S à Sab | Sbd, digantikan oleh:
    S à aScZ1 | dd Z1 | ffZ1
    Z1 à ab | bd
    Z1 à abZ1 | bd Z1

    Hasil akhir setelah penghilangan rekursif kiri adalah:

    S à aSc | dd | ff
    S à aScZ1 | dd Z1 | ffZ1
    Z1 à ab | bd
    Z1 à abZ1 | bd Z1
    Pada kasus di atas S adalah satu-satunya simbol variabel yang menghasilkan produksi rekursif kiri.
    Contoh lain, terdapat tata bahasa bebas konteks:
    S à Sab | Sb | cA
    A à Aa | a | bd
    Pertama-tama kita lakukan pemisahan aturan produksi
    Aturan produksi yang rekursif kiri :
    S à Sab | Sb
    A à Aa
    Dari situ kita tentukan:
    Untuk simbol ruas kiri S: α1= ab, α2 =b
    Untuk simbol ruas kiri A: α1 = a
    Aturan produksi yang tidak rekursif kiri :
    S à cA
    A à a | bd
    Dari situ kita dapatkan
    Untuk simbol ruas kiri S: β1 = cA
    Untuk simbol  ruas kiri A: β1 = a, β2 = bd
    Kita lakukan penggantian aturan produksi yang rekursif kiri:
    Untuk yang memiliki simbol ruas kiri S :
    S à Sab | Sb, digantikan oleh :

    S à cAZ1
    Z1 à ab | b
    Z1 à abZ1 | bZ1

    Untuk yang memiliki simbol ruas kiri A :

    A à Aa, digantikan oleh:
    A à a Z2 | bdZ2
    Z2 à a
    Z2 à a Z2

    Hasil akhir setelah penghilangan rekursif kiri adalah:
    S à cA
    A à a | bd
    S à cAZ1
    Z1 à ab | b
    Z1 à abZ1 | bZ1
    A à a Z2 | bdZ2
    Z2 à a
    Z2 à a Z2
    Perhatikan bahwa penghilangan rekursif kiri memunculkan simbol variabel baru, dan aturan produksi baru yang rekursif kanan.
    Contoh lain, terdapat tata bahasa bebas konteks:
    S à Sa |aAc | c | ε
    A à Ab | ba
    Pertama-tama kita lakukan pemisahan aturan produksi
    Aturan produksi yang rekursif kiri:
    S à Sa
    A à Ab
    Dari situ kita tentukan:
    Untuk simbol ruas kiri S: α1 = a
    Untuk simbol ruas kiri A: α1 = b
    Aturan produksi yang tidak rekursif kiri:
    S à aAc | c | ε
    A à ba
    Dari situ kita dapatkan
    untuk simbol ruas kiri S:β1 = aAc, β2= c, β3 = ε
    untuk simbol ruas kiri A: β1 = ba
    Perhatikan produksi ε termasuk produksi yang tidak rekursif kiri
    Kita lakukan penggantian aturan produksi yang rekursif kiri :
    Untuk yang memilki simbol ruas kiri S :
    S à Sa, digantikan oleh :
    S à aAcZ1 | cZ1 | Z1
    Z1 à a
    Z1 à a Z1

    Untuk yang memiliki simbol ruas kiri A:
    A à Ab, digantikan oleh :
    A à ba Z2
    Z2 à b
    Z2 à bZ2

    Hasil akhir setelah penghilangan rekursif kiri adalah:

    S à aAc | c | ε
    S à aAcZ1 | cZ1 | Z1
    A à ba
    A à ba Z2
    Z1 à a
    Z1 à a Z1
    Z2 à b
    Z2 à b Z2

    7. BENTUK NORMAL GREIBACH

    7.1. Definisi Bentuk Normal Greibach
    Bentuk normal Greibach merupakan bentuk normal yang memiliki banyak konsekuensi teoritis dan prkatis. Dalam bentuk normal Greibach  kita membatasi posisi munculnya terminal-terminal dan variabel-variabel. Suatu tata bahasa bebas konteks (CFG) dikatakan dalam bentuk normal Greibach / Greibach Normal Form,  selanjutnya kita sebut sebagai GNF, jika setiap aturan produksinya ada dalam bentuk:
    A à
    Keterangan :
    A : simbol terminal (tunggal), a ε T
    Α : rangkaian simbol-simbol variabel (V*)
    Atau dengan kata lain, suatu tata bahasa bebas konteks dalam bentuk normal Greibach bila hasil produksinya (ruas kanan) diawali dengan satu simbol terminal, slanjutnya bisa diikuti oleh rangkaian simbol variabel. Contoh tata bahasa bebas konteks dalam bentuk  bentuk normal Greibach:
     S à a | aAB
    A à aB
    B à cS
    Untuk dapat diubah ke dalam bentuk normaol Greibach, tata bahasa semula haru memenuhi syarat:
    • Sudah dalam bentuk normal Chomsky
    • Tidak bersifat rekursif kiri
    • Tidak menghasilkan ε

    Terdapat dua cara pembentukan bentuk normal Greibach , yaitu melalui substitusi dan perkalian matriks. Pada bagian berikutnya kita membahasa kedua cara tersebut.
    7.2. Pembentukan Bentuk Normal Greibach dengan Substitusi
    Secara umum langkah-langkah untuk mendapatkan bentuk normal Greibach :
    1.              Tentukan urutan simbol-simbol variabel yang ada dalam tata bahasa. Misalkan terdapat m variabel dengan urutan A1, A2, ...., Am

    2.            Berdasarkan urutan simbol yang ditetapkan pada langkah (1) seluruh aturan produksi yang ruas kanannya diawali dengan simbol variabel dapat dituliskan dalam bentuk Ah à Ai γ di mana h <> i (rekrusif kiri sudah dihilangkan), γ bisa berupa simbol-simbol variabel :
    a.             Jika h < i, aturan produksu ini sudah benar ( tidakperlu diubah)

    b.            Jika h > i, aturan produksi belum benar. Lakukan substitusi berulang-ulang terhadap Ai (ganti Ai pada produksi ini dengan ruas kanan produksi dari variabel Ai ) sehingga suatu saat diperoleh produksi dalam bentuk Ah à Ap γ (dimana h £ p )
    i)        Jika h = p , lakukan penghilangan rekursif kiri
    ii)       Jika h < p, aturan produksi sudah benar  
          
    3.            Jika terjadi penghilangan rekursif kiri pada tahap (2b), sejumlah simbol variabel baru yang muncul dari operasi ini dapat disisipkan pada urutan variabelsemula dimana saja asalkan ditempatkan tidak sebelum Ah (di kiri)

    4.            Setelah langkah (2) & (3) dikerjakan maka aturan-aturan produksi yang ruas kanannya dimulai simbol variabel sudah berada dalam urutan yang benar
    Ax à Ay g ( di mana x < y )
    Produksi-produksi yang lain ada dalam bentuk:
    Ax à a g ( a = simbol terminal )
    Bx à g
    ( B2 = simbol variabel baru yang akan muncul sebagai akibat dari operasi penghilangan rekursif kiri ).
    5.            Bentuk normal Greibach  diperoleh dengan cara melakukan substitusi mundur mulai dari variabel Am, lalu Am-1, Am-2, ..... Dengan cara ini aturan produksi dalam bentuk Ax à Ay g dapat diubah sehinga ruas kanannya dimulai dengan simbol terminal.

    6.            Produksi dalam bentuk Bx à g juga dapat diubah dengan cara substitusi seperti pada langkah (5).

    Contoh (tata bahasa bebas konteks sudah dalam bentuk normal Chomsky dan memenuhi syarat untuk diubah ke bentuk normal Greibach), simbol awal adalah S:
    S à CA
    A à a | d
    B à b
    C à DD
    D à AB
    Kita tentukan urutan simbol variabel, misalnya S, A, B, C, D (S<A<B<C<D).
    * Perhatikan urutan tersebut boleh anda tentukan sendiri, buatlah urutan sedemikian sehingga memudahkan untuk proses selanjutnya

    Kita periksa aturan produksi yang simbol pertama pada ruas kanan adalah simbol variabel, apakah sudah memenuhi ketentuan urutan variabel:
    §  S à CA ( sudah memenuhi aturan karena S<C)

    §  C à DD (sudah memenuhi karena C<D)

    §  D à AB (tidak memenuhi, karena D>A)

    Yang belum memenuhi urutan yang telah kita tentukan adalah: D à AB, karena ruas kiri > simbol pertama pada ruas kanan. Maka kita lakukan sibstitusi pada simbol variabel A, aturan produksi menjadi :
    D à aB | dB
    Setelah semua aturan produksi sudah memenuhi ketentuan urutan variabel, kita lakukan substitusi mundur pada aturan produksi yang belum dalam bentuk normal Greibach  (‘=>’ dibaca ‘menjadi’):

    §  C à DD => C à aBD | dBD

    §  S à CA => S à aBDA | dBDA

    * Perhatikan substitusi mundur dimulai dari aturan produksi yang memiliki ruas kiri dengan urutan variabel paling akhir ( kasus di atas:S<A<B<C<D, maka C lebih dulu disubstitusikan daripada S ).
    Hasil akhir aturan produksi yang sudah dalam bentuk normal Greibach :
    S à aBDA | dBDA
    A à a | d
    B à b
    C à aBD | dBD
    D à aB | dB
    * Perhatikan : setiap substitusi kita lakukan pada simbol variabel pertamapada ruas kanan ( pada aturan produksi yang belum bentuk normal Greibach tentunya ).
    Prinsipnya :
    • Biarkan aturan produksi yang sudah dalam bentuk normal Greibach

    • Tentukan pengurutan simbol variabel, berdasarkan kondisi aturan produksi yang ada buatlah urutan sedemikian sehingga memudahkan untuk proses selanjutnya. Mulailah terlebih dahulu dari seimbol awal.

    §  Lakukan perubahan pada aturan produksi yang belum memenuhi ketentuan urutan tersebut dan bila perlu selama proses itu bisa dilakukan substitusi dan penghilangan rekursif kiri.

    • Lakukan substitusi mundur sedemikian rupa sehingga semua aturan produksi akan diawali dengan tepat sebuah simbol terminal. Proses substitusi mundur dimulai dari aturan produksi dengan urutan paling akhir.

    • Lakukan substitusi mundur juga pada aturan produksi baru yang muncul sebagai hasil penghilangan rekursif kiri.

    Contoh (simbol awal A) :

    A à BC
    B à CA | b
    C à AB | a
    Kita tentukan urutan simbol: A,B,C ( A<B<C )
    A à BC ( sudah memenuhi karena A<B)
    B à CA (sudah memenuhi karena B<C)
    C à AB (padahal C > A sehingga harus diubah)
    Pengubahan C à AB:
    C à AB => C à BCB => C à CACB | bCB
    Untuk C à CACB lakukan penghilangan rekursif kiri menjadi
    C à bCBZ1 | aZ1
    Z1 à ACB
    Z1 à ACBZ1

    Kita lihat seluruh hasil produksi dari variabel C, sudah dalam bentuk normal Greibach:
    C à bCBZ1 | aZ1 | bCB | a
    Setelah semua aturan produksi sudah memenuhi ketentuan urutan variabel, kita laukan substitusi mundur:
    B à CA => B à bCBZ1A | aZ1A | bCBA | aA
    A à BC => A à bCBZ1AC | aZ1AC | bCBAC | aAC | bC

    Selanjutnya lakukan pula substitusi pada aturan produksi dengan variabel baru yang terbentuk (pada contoh ini Z1) :
    §  Z1 à ACB => Z1 à bCBZ1ACCB | aZ1ACCB | bCBACCB | aACCB | bCCB
    §  Z1 à ACBZ1 => Z1 à bCBZ1ACCBZ1 | aZ1ACCBZ1 | bCBACCBZ1 | aACCBZ1 | bCCBZ1

    Hasil akhir aturan produksi dalam bentuk bentuk normal Greibach :
    A à bCBZ1AC | aZ1AC | bCBAC | aAC | bC |
    B à bCBZ1A | aZ1A | bCBA | aA | B
    C à bCBZ1 | aZ1 | bCB | a
    Z1 à bCBZ1ACCB | aZ1ACCB | bCBACCB | aACCB | bCCB
    Z1 à bCBZ1ACCBZ1 | aZ1ACCBZ1 | bCBACCBZ1 | aACCBZ1 | bCCBZ1

















    Sumber Pustaka :
    Teori Bahasa dan Otomata, Heru Cahya Rustamadji, Fakultas Teknik Industri Universitas Pembangunan Nasional, 2004.
    Computation Engineering : Applied Automata Theory and Logic, Gopalakrishnan, Ganesh, New York : Springer, 2006.
    Introduction to Automata Theory, Languages, and Computation, 2nd Edition, Hopcroft, John E. et al, New York : Addison-Wesley, 2001.


                   


                     





                   
                   

                   



                   


                   







                   


                   


                   





























           






0 komentar:

Poskan Komentar