Grammar dan Bahasa

Anyeonghaseyo cingudeul^^

Assalamu’alakum..

Ketemu lagi dengan saya, apa kabarnya nih? Baik semua kaan hihihi :D;D

Seperti kata saya kemarin, saya akan sering memposting informasi mengenai mata kuliah Teori Bahasa & Otomata. Tapi kali ini berbeda dengan blog kemarin, dengan pembahasan yang lebih menarik lagi yaitu mengenai GRAMMAR & BAHASA. Langsung aja yuk kita simak sama-sama. Ceekiidoooots.......

GRAMMAR, apakah itu?????

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

Aturan Produksi

Aturan produksi dinyatakan dalam bentuk “ α => β “ (bisa dibaca α menghasilkan β, atau dibaca α  menurunkan β)

               #      α merupakan simbol-simbol pada ruas kiri aturan produksi, sedangkan β merupakan simbol-simbol ruas kanan aturan produksi

               #      Simbol-simbol tersebut dapat berupa simbol terminal (Vt) atau simbol NON-Terminal (Vn)/Variabel.

               #      Simbol Vn adalah simbol yang masih dapat diturunkan, biasanya identik dengan huruf besar (‘A’,’B’,’C’)

               #      Simbol Vt adalah simbol yang sudah tidak dapat diturunkan lagi, biasanya identik dengan huruf kecil (‘a’,’b’,’c’)

               #      Dengan menerapkan aturan produksi, suatu grammar bisa menghasilkan sejumlah string.

               #      Contoh aturan produksi :

E => T | T+E | T * E
T => a

Derivasi Kalimat dan Penentuan Bahasa

Cara menentukan derivasi kalimat bahasa dari masing-masing gramar berikut :

G₁ dengan Q₁   = {1. S => aAa,  2. A => aAa,  3. A => b}.

Penyelesaian :

Derivasi kalimat terpendek :        S => aAa (1) 

                                                    S => aba (3)

Derivasi kalimat umum :     S => aAa       (1)

                                             = >aaAaa    (2)

     => aⁿAaⁿ     (2)

                                             => aⁿbaⁿ     (3)

v  Kesimpulan :

                    L₁ (G₁  ) = { aⁿbaⁿ ½ n ³ 1}

Menentukan grammar sebuah bahasa

—  Tentukan sebuah grammar regular untuk bahasa L₁ = { aⁿ | n ≥ 1}

—  Jawab :

Q₁ (L₁ ) = {S => aS | a}
S => a atau
S => aS => aa atau
S => aS => aaS => aaa

Contoh soal

Tentukan sebuah gramar bebas konteks untuk bahasa :

L₃  = himpunan semua identifier yang sah menurut bahasa pemrograman Pascal dengan batasan : terdiri dari simbol huruf kecil dan angka, panjang identifier boleh lebih dari 8 karakter

Penyelesaian :

          Langkah kunci : karakter pertama identifier harus huruf. 

          Buat dua buah himpunan bilangan terpisah : huruf (H) dan angka (A)

          Q₃ (L₃ ) = {S → H|HT, T → AT|HT|H|A,   H → a|b|c|…,  A → 0|1|2|…}

Contoh :

«  G₁ :  V_T = {I,  Love, Miss, You}, V = {S,A,B,C}, P = {S => ABC, A=> I, B=> Love | Miss, C=> You}

«  S => ABC

«     => I loveYou

«  L(G₁)={I love You, I Miss You}

Question & Answer

Tentukan apakah produksi-produksi berikut memenuhi aturan grammar Reguler

Tentukan apakah produksi-produksi berikut memenuhi aturan grammar Bebas Konteks

Tentukan apakah produksi-produksi berikut memenuhi aturan grammar Konteks Sensitive

Tentukan apakah produksi-produksi berikut memenuhi aturan grammar Unrestricted

HIRARKI CHOMSKY

Anyeonghaseyo, chingudeul...

Assalamu’alaikuum,

Kali ini saya akan memposting sedikit materi perkuliahan saya yaitu tentang mata kuliah Teori Bahasa dan Otomata, dengan tema “HIRARKI CHOMSKY”. Mungkin sebagian dari cingu masih asing dengan namanya, pada bertanya-tanya, ‘Apa sih Hirarky Chomsky itu?’. Nah daripada penasaran, mending langsung simak aja yaa Cab Cuuusss.....

HIRARKI CHOMSKY terbagi menjadi 4 bagian, yaitu :

Ø  Tipe / Level 3 (Regular)

Memiliki aturan :

·         Simbol sebelah kiri harus berupa simbol variabel

·         Simbol sebelah kanan maksimal hanya memiliki sebuah simbol variabel (bila ada terletak di paling kanan)

Contoh :

Ø  Tipe / Level 2 (Bebas Konteks)

Memiliki aturan :

·         Simbol sebalah kiri harus simbol variabel

Contoh :

Ø  Tipe / Level 1 (Context sensitive)

Memiliki aturan :

·         Simbol pada ruas sebelah kiri harus minimal ada sebuah variabel

·         |a| <= |b|

Contoh :

Ø  Tipe / Level 0 (Unrectricted)

Memiliki aturan :

·         Simbol ruas sebalah kiri harus minimla ada sebuah simbol variabel

·         Tidak ada batasan pada atuan produksi

Contoh :

          

 Sekian dulu yaa postingan saya kali ini, semoga bermanfaat untuk kalian cinguu.. Terima kasih kamsahamnida telah menyempatkan waktu berkunjung di blog saya, sampai jumpa di postingan yang lain yaak, anyeoong^^