The Gad Blog

BENTUK NORMAL CHOMSKY Bentuk normal Chomsky / Chomsky Normal Form (CNF) merupakan salah satu bentuk normal yang sangat berguna untuk tata bahasa bebas konteks. 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: 1.          Tidak memiliki produksi useless 2.          Tidak memiliki produksi unit 3.          Tidak memiliki produksi ε Aturan produksi dalam bentuk normal Chomsky ruas kanannya tepat berupa sebuah terminal atau dua variabel. Misalkan: A -> BC A -> b B -> a C -> BA | d Pembentukan Bentuk Normal Chomsky   Langkah-langkah pembentukan   bentuk normal C...

A. TEORI BAHASA Teori bahasa membicarakan bahasa formal, terutama untuk kepentingan perancangan kompilator dan pemroses naskah. Bahasa formal adalah kumpulan kalimat dalam sebuah bahasa yang dibangkitkan oleh sebuah tata bahasa yang sama. B. AUTOMATA Automata adalah mesin abstrak yang dapat mengenali,menerima, dan membangkitkan sebuah kalimat dalam bahasa tertentu. Automata merupakan suatu sistem yang terdiri atas sejumlah berhingga state, dimana state menyatakan informasi mengenai input yang lalu dan dapat dianggap sebagai memori mesin. Input pada mesin automata dianggap sebagai bahasa yang harus dikenali oleh mesin. Selanjutnya, mesin automata membuat keputusan yang mengindikasikan apakah input itu diterima atau tidak. C. FINITE STATE AUTOMATA Finite State Automata (FSA) merupakan mesin automata dari bahasa reguler. FSA memiliki state yang banyaknya berhingga dan dapat berpindah – pindah dari satu state ke state yang lain. Perpindahan state dinyatakan d...