aboutCHOMSKY

Sebenernya ini tugas dari dosen aku, tapi karna dikit banged yang bahas soal ini d internet, jadi aku mau share hasil pencarian aku setelah aku combine dari mana-mana. Silahkan di-copy, kalo bisa, tinggalin komen y, berbentuk saran, perbaikan, maupun kritik. Mungkin di posting ini masih banyak kesalahan, maklum, aku juga lagi belajar. Semoga bermanfaat.



1. Tata Bahasa Chomsky

Yaitu aturan yang disebutkan pada proses pengenalan dan pembangkitan kalimat.

Teori bahasa membicarakan bahasa formal (formal language), terutama untuk kepentingan perancangan kompilator (compiler) dan pemroses naskah (text processor)

· Bahasa formal adalah kumpulan kalimat. Semua kalimat dalam sebuah bahasa dibangkitkan oleh sebuah tata bahasa (grammar) yang sama.

· Sebuah bahasa formal bisa dibangkitkan oleh dua atau lebih tata bahasa berbeda.

Secara formal, tata bahasa terdiri dari 4 komponen yaitu :


1. Himpunan berhingga, tidak kosong dari simbol-simbol non terminal T1

2. Himpunan berhingga, dari simbol-simbol non-terminal N

3. Simbol awal S  N, yang merupakan salah satu anggota dari himpunan simbol nonterminal.

4. Himpunan berhingga aturan produksi P yang setiap elemennya dituliskan dalam bentuk : α → β , dimana α dan β adalah string yang dibentuk dari himpunan T u N dan α harus berisi paling sedikit satu simbol non-terminal. Keempat komponen tersebut sering dituliskan sbb : G = (T,N,S,P).

Bahasa yang dihasilkan oleh G ditulis sebagai L(G), yaitu himpunan string yang dapat diturunkan dari simbol awal S dengan menerapkan aturan-aturan produksi yang terdapat pada P.

Aturan Produksi

Aturan produksi α→β yang diterapkan pada suatu string w=aαc mengganti kemunculan. α menjadi β, sehingga string tersebut berubah menjadi w=aβc, sehingga dapat dituliskan aαc => aβc (aαc memproduksi aβc). Produksi tersebut dapat diterapkan berkali-kali

w1 => w2 => w3 => … => wn

atau dapat dituliskan

w1 =>* wn

jika minimal harus ada 1 aturan produksi yang diterapkan :

w1 =>+ wn

Contoh

Tatabahasa G = {{S} , {a,b}, S , P } dengan aturan produksi P adalah

S → aSb

S → ε

maka dapat dihasilkan suatu string

S -> aSb -> aaSbb ->aabb

sehingga dapat dituliskan

S ->* aabb

Bahasa yang dihasilkan dari tatabahasa tersebut adalah

L(G) = { ε , ab, aabb , aaabbb , aaaabbbb, … }

atau dapat pula dituliskan

L(G) = {anbn | n ≥ 0 }



2. Hirarki Chomsky

Pada tahun 1959 Noam Chomsky menggolongkan tingkatan bahasa menjadi empat yaitu:

Type 3. Bahasa Regular

– Mesin Otomata : FSA meliputi DFA & NFA

– Aturan Produksi :

• α adalah sebuah simbol variabel,

• β maksimal memiliki sebuah simbol variabel yang bila ada terletak di posisi paling kanan.

Bahasa regular, batasan ruas kanan maksimal memiliki sebuah simbol variabel yang terletak di paling kanan.

Bahasa regular bisa memiliki simbol terminal saja dalam jumlah tidak dibatasi, tetapi bila terdapat simbol variabel,maka simbol tersebut hanya berjumlah 1 dan terletak di posisi paling kanan

Contoh :

• A _ e

• A _ efg

• A _ efgH

• C _ D

Type 2. Bahasa Bebas Konteks

– Mesin Otomata : PDA

– Aturan Produksi : α berupa sebuah simbol variabel.

Variable

• Bahasa bebas konteks : batasan ruas kiri haruslah

tepat satu simbol variabel

– Contoh :

• B_ CDeFg

• D_ BcDe

• Bahasa bebas konteks menjadi dasar dalam pembentukan suatu parser/proses analisis sintaksis yang dideskripsikan secara formal dengan notasi BNF (Backus Normal Form)

Type 1. Bahasa Context Sensitive

– Mesin Otomata : Linier Bounded Automata

– Aturan Produksi : |α|≤ |β|

• Batasan context sensitive digunakan dalam

– proses analisis semantik pada tahap kompilasi

Type 0. Bahasa Unrestricted / Natural Language

– Mesin Otomata : Mesin Turing

– Aturan Produksi : tidak ada batasan