Teori Bahasa dan Otomata

Pendahuluan

Dengan adanya blog ini maka saya bertujuan untuk memberikan sedikit rangkuman materi dari setiap materi yang telah disampaikan oleh dosen dan sebagai pelengkap tugas dari mata kuliah TBO

Pada blog ini akan ada beberapa materi yang ada diantaranya:

1. Pengantar Teori Bahasa dan Otomata

2. Hirarki Chomsky

#Materi 1

Pengantar Teori Bahasa dan Otomata

Bahasa

Bahasa bisa juga disebut sebagai rangkaian simbol-simbol yang mempunyai makna

Otomata

• Otomata merupakan suatu sustem yang terdiri atas sejumlah state, dimana state menyatakan informasi mengenai input.
• Otomata juga dianggap sebagai mesin otomatis (bukkan mesin fisik) yang merupakan suatu model matematika daru suatu sistem yang menerima input dan menghasilkan output

Bahasa & Otomata

Hubungan di antara bahasa dan otomata adalah bahasa dijadikan sebagai input oleh suatu mesin otomata, selanjutnya mesin otomata akan membuat keputusan yang mengindikasikan apakah input itu diterima atau ditolak.

Misalnya, kita memiliki sebuah mesin sederhana yang menerima input kata dalam bahasa indonesia, hal ini bisa dilihat pada gambar disamping. Pada gambar disamping, bila mesin mendapat string input berikut:

1. ada : diterima

2. adu : diterima

3. add : ditolak

Penjelasannya adalah:

• Sebuah string input diterima bila mencapai state akhir / final state yang pada contoh diatas digambarkan dengan lingkaran ganda.
• Mesin ini memiliki 6 state yaitu { q0, q1, q2, q3, q4, q5 } yang merupakan himpunan state yang ada pada mesin tersebut.
• State awal dari mesin adalah q0.
• { q3, q4 } adalah himpunan state akhir atau final state.
• Sedangkan simbol input adalah { a, d, u }.

Teori Bahasa adalah konsep-konsep pada "string alphabet" dalam penyambungan karakter-karakter alpabet untuk membentuk suatu makna (bahasa).

Alpabet adalah himpunan simbol (karakter) tidak kosong dan berhingga. Alpabet dilambangkan dengan ∑

Konsep Teori Bahasa dan Otomata

• String adalah deretan simbol dari alpabet dimana perulangan simbol diijinkan. Contoh: 

            V = {a,b,c,d}

            String pada alpabet V antara lain -> 'a', 'abcd','bbba'

• Panjang String adalah jumlah simbol di dalam string pada alpabet dan pengulangan. kemunculan simbol dihitunh. Panjang string dilambangkan |w|. Contoh:

            |ε| = 0

            |a| = 1

            |aa| = 2

            |aaa| = 3

            |aaab| = 4

Empty String (null string) adalah string yang tidak mengandung simbol apapun. Lambangnya e atau l

Regular Expression adalah cara untuk mengekspresikan bahasa dengan hanya menggunakan operasi:

• Concatenation (Penyambungan)
• Superscript (Perkalian)
• Kleene Closure (String Tanpa Simbol)
• Positif closure (Tidak Ada String Kosong Didalamnya)

#Materi 2

Hirarki Chomsky

• Secara umum tata bahasa dirumuskan sebagai berikut: a -> b yang berarti a menghasilkan b atau a menurunkan b.
• Simbol variabel / non teminal adalah simbol yang masih bisa diturunkan dan ditandai dengan huruf besar seperti A, B, C, dst.
• Simbol terminal adalah simbol yang sudah tidak bisa diturunkan dan ditandai dengan huruf kecil seperti a, b, c, d, dst.

Contoh Aturan Produksi

• T -> a

        dibaca "T menghasilkan a"

• E -> T | T + E

        dibaca "E Menghasilkan T" atau

                   "E Menghasilkan T dan E"

    Simbol | menyatakan 'atau', digunakan untuk mempersingkat penulisan aturan produksi yang mempunyai ruas kiri yang sama.

Tipe 0 / Unrestricted / Natural Language

Aturan:

• Simbol pada ruas sebelah kiri harus minimal ada sebuah simbol variabel
• Tidak ada batasan pada aturan produksinya.
• Misal: Abc -> De (Diterima)

                    ABC -> b (diterima)

                    abc -> GHI (ditolak)

Tipe 1/ Conteks Sensitive

Aturan:

• Simbol pada ruas sebelah kiri harus minimal ada sebuah simbol variabel
• Panjang string pada ruas kiri  ≤ panjang string pada ruas kanan

         |a| ≤ |b|

        Misal:

        Ab -> DeF (diterima)

        CD -> eF (diterima)

        exception:S -> ε (diterima)

        ABC -> DE (ditolak)

Tipe 2 / Bebas Konteks / Context Free

Aturan:

• Simbol pada sebelah kiri harus berupa sebuah simbol variabel

            B -> CDeFG (diterima)

            D -> BcDe (diterima)

            a -> b (ditolak)

Tipe 3 / Reguler Grammer

Aturan:

• Simbol pada sebelah kiri harus berupa sebuah simbol variabel
• Simbol pada sebelah kanan maksimal hanya memiliki sebuah simbol varibel dan bila ada terletak diposisi paling kanan

    A -> e (diterima)

    A -> fgh (diterima)

    A -> eH (diterima)

    C -> D (diterima)

    A -> Bc (ditolak)

#materi 3

Grammar dan Bahasa

Grammar adalah sebagai kumpulan dari himpunanhimpunan variabel, simbolsimbol terminal, simbol awal, yang dibatasi oleh aturan-aturan produksi. Aturan produksi merupakan pusat dari grammar yang menspesifikasikan bagaimana suatu grammar melakukan transformasi suatu string atau karakter ke bentuk lainnya.

    Semua aturan produksi dinyatakan dalam bentuk “α → β “ (bisa dibaca α menghasilkan β, atau dibaca α menurunkan β). α merupakan simbol-simbol pada ruas kiri aturan produksi, sedangkan β merupakan simbolsimbol ruas kanan aturan produksi. 

Grammar (G) didefinisikan sebagai pasangan 4 tuple : 

VT , VN , S, dan Q, dan dituliskan sebagai G(VT , VN , S, Q), dimana : 

VT : himpunan simbol-simbol terminal (atau himpunan token-token, atau alfabet) 

VN : himpunan simbol-simbol non terminal 

S : simbol awal (atau simbol start) 

Q : himpunan produks

Analisa Penentuan Type Grammar

• Grammar G1 dengan Q1 = {S → aB, B → bB, B → b}. 

    Ruas kiri semua produksinya terdiri dari sebuah VN maka G1 kemungkinan tipe CFG atau RG. Selanjutnya karena semua ruas kanannya terdiri dari sebuah VT atau string VT VN maka G1 adalah RG. 

• Grammar G2 dengan Q2 = {S → Ba, B → Bb, B → b}.

    Ruas kiri semua produksinya terdiri dari sebuah VN maka G2 kemungkinan tipe CFG atau RG. Selanjutnya karena semua ruas kanannya terdiri dari sebuah VT atau string VNVT maka G2 adalah RG.

• Grammar G3 dengan Q3 = {S → Ba, B → bB, B → b}.

    Ruas kiri semua produksinya terdiri dari sebuah VN maka G3 kemungkinan tipe CFG atau RG. Selanjutnya karena ruas kanannya mengandung string VT VN (yaitu bB) dan juga string VNVT (Ba) maka G3 bukan RG, dengan kata lain G3 adalah CFG.

• Grammar G4 dengan Q4 = {S → aAb, B → aB}.

    Ruas kiri semua produksinya terdiri dari sebuah VN maka G4 kemungkinan tipe CFG atau RG. Selanjutnya karena ruas kanannya mengandung string yang panjangnya lebih dari 2 (yaitu aAb) maka G4 bukan RG, dengan kata lain G4 adalah CFG.

• Grammar G5 dengan Q5 = {S → aA, S → aB, aAb → aBCb}.

    Ruas kirinya mengandung string yang panjangnya lebih dari 1 (yaitu aAb) maka G5 kemungkinan tipe CSG atau UG. Selanjutnya karena semua ruas kirinya lebih pendek atau sama dengan ruas kananya maka G5 adalah CSG.

• Grammar G6 dengan Q6 = {aS → ab, SAc → bc}. 

                                                {S → aA, S → aB, aAb → aBCb}.

    Ruas kirinya mengandung string yang panjangnya lebih dari 1 maka G6 kemungkinan tipe CSG atau UG. Selanjutnya karena terdapat ruas kirinya yang lebih panjang daripada ruas kanannya (yaitu SAc) maka G6 adalah UG.

Contoh Derivasi Kalimat dan Penentuan Bahasa

1. Tentukan bahasa dari masing-masing gramar berikut : 

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

Jawab : 

Derivasi kalimat terpendek :                                 Derivasi kalimat umum : 

S → aAa (1)                                                            S → aAa (1) 

   → aba (3)                                                                → aaAaa (2) 

                                                                                   ......

                                                                                   → a^nAa^n (2) 

                                                                                   → a^nba^n (3) 

• Dari pola kedua kalimat disimpulkan : L1 (G1 ) = { a^nba^n → n → 1}

2. Tentukan bahasa dari masing-masing gramar berikut : 

G3 dengan Q3 = { 1. S → aSBC, 

                               2. S → abC, 

                               3. bB → bb, 

                               4. bC → bc, 

                               5. CB → BC, 

                               6. cC → cc}

Jawab :

Derivasi kalimat terpendek :

S → abC (1)

S → abc (4)

Derivasi kalimat terpanjang :

S → aSBC (1)

S → aaSBCBC (1)

S → aaabCBCBC (1)

S → aaabBCCBC (5)

S → aaabBCBCC (5)

S → aaabbBCCC (3)

S → aaabbbCCC (3)

S → aaabbbcCC (4)

S → aaabbbccC (6)

S → aaabbbccc (4)

(G2 ) = { a^nb^nc^n | n >= 1}