Teknologi Informasi

TUGAS TBO GRAMMAR DAN BAHASA HIRARKI CHOMSKY Assalamualaikum wr.wb Teman- teman k ali ini saya akan memposting mengenai Teori Bahasa dan Otomata. Khususnya mengenai “Hirarki Chomsky”.  Dalam hirarki Chomsky a da 4(empat) kelas pengelompokan suatu bahasa, yaitu: 1.        Reguler (Level/Tipe 3) Mesin Automata :  Finate State Automata. DFA dan NFA Aturan:- Simbol sebelah kiri harus berupa simbol variabel. -      Simbol sebelah kanan maksimal hanya memiliki simbol variabel dan bila ada terletak di paling kanan 2.        Bebas konteks (Level/Tipe 2) Mesin Automata :  Push Down Automata Aturan:- Simbol sebelah kiri harus simbol variabel 3.        Context Sensitive (Level/Tipe1) Mesin Automata : Linier Bounded Automata Aturan:- Simbol pada ruas sebelah kiri harus minimal ada sebuah variabel -      |a| ≤ |b| ...

  EKUIVALENSI ANTAR DETERMINISTIC FINITE AUTOMATA ( REDUKSI ) Ekuivalensi Antar Deterministic Finite Automata Untuk suatu bahasa regular, kemungkinan ada sejumlah  Deterministic Finite Automata   yang dapat menerimanya. Perbedaannya hanyalah jumlah  state yang dimiliki otomata - otomata yang saling ekuivalen tersebut. Tentu saja, dengan alasan kepraktisan, kita memilih otomata dengan jumlah  state yang lebih sedikit. Sasaran : mengurangi jumlah  state dari suatu Finite State Automata, dengan tidak mengurangi kemampuannya semula untuk menerima suatu bahasa. Istilah yang digunakan  : 1.  Distinguishable :  dapat dibedakan. 2.  Indistinguishable :  tidak dapat dibedakan. Dua DFA M1 dan M2 dinyatakan ekivalen apabila L(M1) = L(M2) Reduksi Jumlah State Pada FSA Reduksi dilakukan untuk mengurangi jumlah state tanpa mengurangi kemampuan untuk menerima suatu bahasa seperti semula (efisiensi) ....

Grammar dan Bahasa *Grammar  : kumpulan dari himpunan simbol-simbol variabel, simbol terminal, simbol awal, yang dibatasi oleh aturan produksi *Aturan produksi : pusat dari grammar yang menspesifikasikan bagaimana suatu grammar dapat melakukan transformasi suatu string atau karakter lainnya *Aturan produksi :  α   à   β   * Simbol - simbol tersebut dapat berupa : Simbol non terminal / variabel (Vn) : simbol yang masih dapat diturunkan lagi,biasanya identik dengan huruf besar.  ex : A,B,C,D,..........dst. Simbol terminal (Vt) : simbol yang sudah tidak dapat diturunkan lagi,biasanya identik dengan huruf kecil. ex : a,b,c,d,.............dst. *Dengan menerapkan aturan produksi, suatu grammar dapat menghasilkan sejumlah String. Contoh :  Pada aturan produksi berikut : E  à  T | T+E | T * E T  à  a *E   à   T            T   à   a *E  à  T+...

Finite State Otomata Finite State Otomata (FNS) ·FSA (Finite State Automata) merupakan tool yang sangat berguna dalam perancangan lexical analyzer, yaitu bagian dari kompilator yang mengelompokan karakter -karakter ke dalam sebuah token, yang berupa unit terkecil seperti nama, variabel, dan keyword. · FSA dipakai untuk penganalisa leksikal dan dipakai juga dalam text editor, pemrosesan teks, dan program file-searching · Model matematika suatu sistem yang menerima input dan output diskrit · Mesin automata dari bahasa Regular · Tidak memiliki tempat penyimpanan sehingga kemampuan mengingat terbatas (contoh: elevator/lift) · Aplikatif – berguna untuk merancang sistem nyata. · Aplikasi meliputi : analisis leksikal, text-editor, protokol komunikasi jaringan (kermit) dan parity checker pengecek parity). FSA atau AH (Automata Hingga) didefinisikan sebagai pasangan 5 tupel → M = (Q, ∑, δ, S,...

Resume Pengantar Teori Bahasa dan Automata TEORI BAHASA 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 b ahasa berbeda. Dikatakan bahasa formal karena grammar diciptakan mendahului pembangkitan setiap kalimatnya. Tata bahasa (grammar) adalah kaidah/aturan pembentukan kata/kalimat. Pada pembahasannya, bahasa formal hanya disebut bahasa saja. Bahasa dalam bentuk tulisan terdiri atas simbol-simbol satuan yang jika dikombinasikan akan mempunyai arti yang berbeda. Simbol-simbol yang biasa dipergunakan dalam sebuah bahasa terbatas jumlahnya, yang membentuk sebuah himpunan dan disebut sebagai abjad/alphabet. Namun kadangkala digunakan istilah karakter yang artinya s...