Tugas(Teori Bahasa&Otomata)

Mikroprosessor

         Mikroprosesor adalah suatu komponen yang berbentuk chip IC (Integrated Circuit) yang terdiri dari beberapa rangkaian yaitu ALU (Arithmatic Logic Unit), CU ( Control Unit), dan Register. Mikroprosesor juga disebut juga sebagai CPU (Central Processing Unit) dan merupakan komponen yang sangat penting di dalam sistem komputer. Mikroprosesor berfungsi sebagai pusat untuk memproses data di dalam sistem komputer.

Bagian terpenting dari prosesor terbagi menjadi 3 yaitu :

• Aritcmatics Logical Unit (ALU), adalah alat yang melakukan pelaksanaan dasar seperti pelaksanaan aritmatika (tambahan, pengurangan, dan semacamnya), pelaksanaan logis (AND, OR, NOT), dan pelaksanaan perbandingan (misalnya, membandingkan isi sebanyak dua slot untuk kesetaraan). Pada unit inilah dilakukan "kerja" yang nyata;
•  Control Unit (CU), merupakan suatu alat pengontrolan yang berada dalam komputer yang memberitahukan unit masukan mengenai jenis data, waktu pemasukan, dan tempat penyimpanan didalam primary storage. Control unit juga bertugas memberitahukan kepada arithmatic logic unit mengenai operasi yang harus dilakukan, tempat data diperoleh, dan letak hasil ditempatkan Perangkat-perangkat alat proses bersertaperlengkapan;
• Memory Unit (MU), merupakan bagian dari processor yang menyimpan alamat-alamat register data yang diolah oleh ALU dan CU.

Sejarah Perkembangan Mikroprocessor :
1971: 4004 Microprocessor
Pada tahun 1971 munculah microprocessor pertama Intel , microprocessor 4004 ini digunakan pada mesin kalkulator Busicom. Dengan penemuan ini maka terbukalah jalan untuk memasukkan kecerdasan buatan pada benda mati.
1972: 8008 Microprocessor
Pada tahun 1972 munculah microprocessor 8008 yang berkekuatan 2 kali lipat dari pendahulunya yaitu 4004.
1974: 8080 Microprocessor
Menjadi otak dari sebuah komputer yang bernama Altair, pada saat itu terjual sekitar sepuluh ribu dalam 1 bulan
1978: 8086-8088 Microprocessor
Sebuah penjualan penting dalam divisi komputer terjadi pada produk untuk komputer pribadi buatan IBM yang memakai prosesor 8088 yang berhasil mendongkrak nama intel.
1982: 286 Microprocessor
Intel 286 atau yang lebih dikenal dengan nama 80286 adalah sebuah processor yang pertama kali dapat mengenali dan menggunakan software yang digunakan untuk processor sebelumnya.
1985: Intel386™ Microprocessor
Intel 386 adalah sebuah prosesor yang memiliki 275.000 transistor yang tertanam diprosessor tersebut yang jika dibandingkan dengan 4004 memiliki 100 kali lipat lebih banyak dibandingkan dengan 4004
1989: Intel486™ DX CPU Microprocessor
Processor yang pertama kali memudahkan berbagai aplikasi yang tadinya harus mengetikkan command-command menjadi hanya sebuah klik saja, dan mempunyai fungsi komplek matematika sehingga memperkecil beban kerja pada processor.
1993: Intel® Pentium® Processor
Processor generasi baru yang mampu menangani berbagai jenis data seperti suara, bunyi, tulisan tangan, dan foto.
1995: Intel® Pentium® Pro Processor
Processor yang dirancang untuk digunakan pada aplikasi server dan workstation, yang dibuat untuk memproses data secara cepat, processor ini mempunyai 5,5 jt transistor yang tertanam.
1997: Intel® Pentium® II Processor
Processor Pentium II merupakan processor yang menggabungkan Intel MMX yang dirancang secara khusus untuk mengolah data video, audio, dan grafik secara efisien. Terdapat 7.5 juta transistor terintegrasi di dalamnya sehingga dengan processor ini pengguna PC dapat mengolah berbagai data dan menggunakan internet dengan lebih baik.
1998: Intel® Pentium II Xeon® Processor
Processor yang dibuat untuk kebutuhan pada aplikasi server. Intel saat itu ingin memenuhi strateginya yang ingin memberikan sebuah processor unik untuk sebuah pasar tertentu.
1999: Intel® Celeron® Processor
Processor Intel Celeron merupakan processor yang dikeluarkan sebagai processor yang ditujukan untuk pengguna yang tidak terlalu membutuhkan kinerja processor yang lebih cepat bagi pengguna yang ingin membangun sebuah system computer dengan budget (harga) yang tidak terlalu besar. Processor Intel Celeron ini memiliki bentuk dan formfactor yang sama dengan processor Intel jenis Pentium, tetapi hanya dengan instruksi-instruksi yang lebih sedikit, L2 cache-nya lebih kecil, kecepatan (clock speed) yang lebih lambat, dan harga yang lebih murah daripada processor Intel jenis Pentium. Dengan keluarnya processor Celeron ini maka Intel kembali memberikan sebuah processor untuk sebuah pasaran tertentu.
1999: Intel® Pentium® III Processor
Processor Pentium III merupakan processor yang diberi tambahan 70 instruksi baru yang secara dramatis memperkaya kemampuan pencitraan tingkat tinggi, tiga dimensi, audio streaming, dan aplikasi-aplikasi video serta pengenalan suara.
1999: Intel® Pentium® III Xeon® Processor
Intel kembali merambah pasaran server dan workstation dengan mengeluarkan seri Xeon tetapi jenis Pentium III yang mempunyai 70 perintah SIMD. Keunggulan processor ini adalah ia dapat mempercepat pengolahan informasi dari system bus ke processor , yang juga mendongkrak performa secara signifikan. Processor ini juga dirancang untuk dipadukan dengan processor lain yang sejenis.
2000: Intel® Pentium® 4 Processor
Processor Pentium IV merupakan produk Intel yang kecepatan prosesnya mampu menembus kecepatan hingga 3.06 GHz. Pertama kali keluar processor ini berkecepatan 1.5GHz dengan formafactor pin 423, setelah itu intel merubah formfactor processor Intel Pentium 4 menjadi pin 478 yang dimulai dari processor Intel Pentium 4 berkecepatan 1.3 GHz sampai yang terbaru yang saat ini mampu menembus kecepatannya hingga 3.4 GHz.
2001: Intel® Xeon® Processor
Processor Intel Pentium 4 Xeon merupakan processor Intel Pentium 4 yang ditujukan khusus untuk berperan sebagai computer server. Processor ini memiliki jumlah pin lebih banyak dari processor Intel Pentium 4 serta dengan memory L2 cache yang lebih besar pula.
2001: Intel® Itanium® Processor
Itanium adalah processor pertama berbasis 64 bit yang ditujukan bagi pemakain pada server dan workstation serta pemakai tertentu. Processor ini sudah dibuat dengan struktur yang benar-benar berbeda dari sebelumnya yang didasarkan pada desain dan teknologi Intel’s Explicitly Parallel Instruction Computing ( EPIC ).
2002: Intel® Itanium® 2 Processor
Itanium 2 adalah generasi kedua dari keluarga Itanium
2003: Intel® Pentium® M Processor
Chipset 855, dan Intel® PRO/WIRELESS 2100 adalah komponen dari Intel® Centrino™. Intel Centrino dibuat untuk memenuhi kebutuhan pasar akan keberadaan sebuah komputer yang mudah dibawa kemana-mana.
2004: Intel Pentium M 735/745/755processors
Dilengkapi dengan chipset 855 dengan fitur baru 2Mb L2 Cache 400MHz system bus dan kecocokan dengan soket processor dengan seri-seri Pentium M sebelumnya.
2004: Intel E7520/E7320 Chipsets
7320/7520 dapat digunakan untuk dual processor dengan konfigurasi 800MHz FSB, DDR2 400 memory, and PCI Express peripheral interfaces.
2005: Intel Pentium 4 Extreme Edition 3.73GHz
Sebuah processor yang ditujukan untuk pasar pengguna komputer yang menginginkan sesuatu yang lebih dari komputernya, processor ini menggunakan konfigurasi 3.73GHz frequency, 1.066GHz FSB, EM64T, 2MB L2 cache, dan HyperThreading.
2005: Intel Pentium D 820/830/840
Processor berbasis 64 bit dan disebut dual core karena menggunakan 2 buah inti, dengan konfigurasi 1MB L2 cache pada tiap core, 800MHz FSB, dan bisa beroperasi pada frekuensi 2.8GHz, 3.0GHz, dan 3.2GHz. Pada processor jenis ini juga disertakan dukungan HyperThreading.
2006: Intel Core 2 Quad Q6600
Processor untuk type desktop dan digunakan pada orang yang ingin kekuatan lebih dari komputer yang ia miliki memiliki 2 buah core dengan konfigurasi 2.4GHz dengan 8MB L2 cache (sampai dengan 4MB yang dapat diakses tiap core ), 1.06GHz Front-side bus, dan thermal design power ( TDP )
2006: Intel Quad-core Xeon X3210/X3220
Processor yang digunakan untuk tipe server dan memiliki 2 buah core dengan masing-masing memiliki konfigurasi 2.13 dan 2.4GHz, berturut-turut , dengan 8MB L2 cache ( dapat mencapai 4MB yang diakses untuk tiap core ), 1.06GHz Front-side bus, dan thermal design power (TDP)

Karakteristik Mikroprosesor

Berikut adalah karakteristik penting dari mikroprosesor :

1. Ukuran bus data internal (internal data bus size): Jumlah saluran yang terdapat dalam mikroprosesor yang menyatakan jumlah bit yang dapat ditransfer antar komponen di dalam mikroprosesor.
2. Ukuran bus data eksternal (external data bus size): Jumlah saluran yang digunakan untuk transfer data antar komponen antara mikroprosesor dan komponen-komponen di luar mikroprosesor.
3. Ukuran alamat memori (memory address size): Jumlah alamat memori yang dapat dialamati oleh mikroprosesor secara langsung.
4. Kecepatan clock (clock speed): Rateatau kecepatan clock untuk menuntun kerja mikroprosesor.
5. Fitur-fitur spesial (special features): Fitur khusus untuk mendukung aplikasi tertentu seperti fasilitas pemrosesan floating point, multimedia dan sebagainya.

Faktor lain yang mempengaruhi kecepatan adalah :

•  Dual-Core mampu memproses beberapa aplikasi secara paralel. Dengan Hyper-Threading, beberapa tugas dijalankan melalui satu arus, tapi dengan dual-core, tugas-tugas ini dipisah menjadi dua arus dan tiap arus diproses sendiri-sendiri.
• Hyper-Threading (HT) memungkinkan 2 pekerjaan untuk dijalankan pada saat yang sama (paralel). Dengan HT, anda bisa menjalankan beberapa aplikasi sekaligus tanpa merasakan lagging/lamban.
• L2 Cache: memori kecepatan tinggi tempat menyimpan data yang sering dipakai oleh CPU. RAM juga memori tetapi aksesnya lebih lamban. PC dengan L2 Cache yang besar memungkinkan lebih banyak data yang bisa diakses dari memori ini sehingga keseluruhan sistem bekerja lebih cepat. Cache ini disebut juga secondary cache dan mempunyai chip sendiri; sedangkan primary cache biasanya didalam CPU itu sendiri. Ukurang cache ada yang 512Kb sampai 2Mb atau lebih.
• Front Side Bus: Mempengaruhi kecepatan data transfer dari CPU ke RAM dan graphics card dan sebaliknya. PC dengan FSB yang tinggi cocok untuk games dan digital media.
• Execute Disable Bit: Menurunkan ancaman sekuriti dari virus seperti memory buffer overflow dimana aplikasi anti-virus tidak bisa menanggulangi.
• Enhanced Intel SpeedStep: Menyediakan kemampuan yang maksimal jika diperlukan dan mengurangi jika tidak. Lebih sering dipakai di laptop atau notebook untuk mengirit penggunaan listrik dari baterai.
• Extended Memory 64 (64-bit): Sistem dengan 32-bit CPU mempunyai maksimum kapasitas 4GB untuk RAM. Untuk menjalankan aplikasi yang besar dan memerlukan memori lebih besar dari 4GB, data extra akan ditulis di hard-disk sehingga memperlambat prosesnya.

Jenis-jenis Processor :

• Socket, yaitu berbentuk kotak persegi yang terdapat pin (kaki) konektor;
• Slot, yaitu berbentuk batangan yang ditancapkan pada port yang khusus disediakan untuk processor model slot. Pada umumnya processor jenis slot banyak ditemukan untuk komputer Pentium II dan Pentium III.

Organisasi Berkas - Berkas Sekuensial(Sistem Berkas)

Sebelumnya pada matakuliah sistem berkas saya memposting materi tentang manajemen file, kali ini akan membahass

Organisasi Berkas – Berkas Sekuensial

semoga dapat membantu ya^^ 

Dalam menggorganisasi berkas secara Sekuensial, Langsung, maupun Sekuensial Berindeks memiliki cara yang berbeda dalam penyusunan rekaman-rekaman yang membentuk berkas / file tersebut.

Rekaman-rekaman data tersebut tersusun atas sejumlah medan Data.

Medan Data : Nilai Dasar yang membentuk sebuah rekaman Data

Rekaman Data : Koleksi Berbagai Medan yang berisi beberapa item data elementer

Berkas Data : koleksi dari rekaman-rekaman yang sama, yang diletakan dalam peralatan penyimpanan data komputer

Pencarian Berkas Secara Sekuensial

Pencarian berkas secara sekuensial dilakukan dengan memproses rekaman-rekaman dalam berkas sesuai dengan urutan keberadaan rekaman-rekaman tersebut sampai ditemukan rekaman-rekaman yang diinginkan atau semua rekaman akan terbaca.

Contoh “nama mahasiswa” merupakan subskrip dalam pencarian pembacaan rekaman dengan “nama mahasiswa” = “Dewi Sartika”

Untuk mencari nama “Dewi Sartika”, diperlukan probe sejumlah 5 kali 

Permasalahan yang muncul bila rekaman berada pada urutan belakang, maka pembacaan akan semakin lama. Dan apabila nama yang dicari tidak ada dalam rekaman, maka aplikasi harus membaca semua rekaman & berakshir denganm pesan “Rekaman tidak ditemukan”

Agar kinerja pembacaan rekaman lebih baik maka salah satu alternatif yang dapat dilakukan adalah rekaman-rekaman dalam berkas tersebut DIURUTKAN untuk mendapatkan pengurutan yang linier berdasar pada nilai kunci rekaman tersebut (bisa alfabetis maupun numeris)

Kolom “Nama Mahasiswa” menunjukan nilai yang urut dari kecil ke besar

Hasil pengurutan (menurut nama mahasiswa) adalah sebagai berikut 

Setelah data tersebut diurutkan maka pembacaan secara sekunsial dalam pemprosesan pencarian nama 

“Dewi Sartika” hanya diperlukan 2 probe

lebih kecil dibandingkan sebelum berkas diurutkan.

Pencarian Biner (Binary Search)

Untuk sebuah berkas yang sudah di urutkan, jumlah probe yang diperlukan untuk membaca sejumlah rekaman dapat di usahakan untuk diperkecil lagi dengan menggunakan teknik pencarian biner. 

Jika Kuncicari < Kuncitengah, maka bagian berkas mulai dari Kuncitengah sampai akhir berkas dielaminiansi.

Contoh 1

Cari rekaman dengan kunci 49 .... ?

1  2      3         4       5          6         7        8       9

Iterasi 1 : [21, 25, 28, 33, 38, 39, 48, 49, 69]

Iterasi 2 :  21, 25, 28, 33, 38, [39, 48, 49, 69]

Iterasi 3 :  21, 25, 28, 33, 38, 39, 48, [49, 69]

Perhitungan :

Iterasi 1 : TENGAH1 = [1+9)/2] = 5

  Kuncicari : Kuncitengah à 49 > 38

à AWAL = TENGAH1  + 1 = 5+1 = 6

1     2          3      4        5         6       7        8        9

 Iterasi 1 : [21, 25, 28, 33, 38, 39, 48, 49, 69]

Perhitungan :

Iterasi 2 : TENGAH2 = [6+9)/2] = 7

    Kuncicari : Kuncitengah à 49 > 48

à AWAL = TENGAH2  + 1 = 7+1 = 8

  1        2    3        4        5         6       7        8        9

Iterasi 2 :  21, 25, 28, 33, 38, [39, 48, 49, 69] Perhitungan :

Iterasi 3 : TENGAH3 = [8+9)/2] = 8

    Kuncicari : Kuncitengah à 49 = 49

à Ketemu, Probe = 3

  1        2    3        4        5       6        7          8        9

Iterasi 3 :  21, 25, 28, 33, 38, 39, 48, [49, 69]

Contoh 2

Cari rekaman dengan kunci 27 .... ?

1  2      3         4       5          6         7        8       9

Iterasi 1 : [21, 25, 28, 33, 38, 39, 48, 49, 69]

Iterasi 2 :  [21, 25, 28, 33], 38, 39, 48, 49, 69

Iterasi 3 :  21, 25, [28, 33], 38, 39, 48, 49, 69

Iterasi 4 :  21, 25], [28, 33, 38, 39, 48, 49, 69

Perhitungan :

Iterasi 1 : TENGAH1 = [1+9)/2] = 5

  Kuncicari : Kuncitengah à 27 < 38

à AKHIR = TENGAH1  - 1 = 5-1 = 4

 1       2      3   4       5          6      7        8       9

Iterasi 1 : [21, 25, 28, 33, 38, 39, 48, 49, 69]

Perhitungan :

Iterasi 2 : TENGAH2 = [1+4)/2] = 2

    Kuncicari : Kuncitengah à 27 > 25

à AWAL = TENGAH2  + 1 = 2+1 = 3

 1       2      3   4       5          6      7        8       9

Iterasi 1 : [21, 25, 28, 33, 38, 39, 48, 49, 69]

Perhitungan :

Iterasi 2 : TENGAH2 = [1+4)/2] = 2

    Kuncicari : Kuncitengah à 27 > 25

à AWAL = TENGAH2  + 1 = 2+1 = 3

   1       2  3   4          5          6      7        8       9

Iterasi 2 :  [21, 25, 28, 33], 38, 39, 48, 49, 69

Perhitungan :

Iterasi 3 : TENGAH3 = [3+4)/2] = 3

    Kuncicari : Kuncitengah à 27 < 28

à AKHIR = TENGAH3  - 1 = 3-1 = 2

   1       2  3     4          5          6      7        8       9

Iterasi 3 :  21, 25, [28, 33], 38, 39, 48, 49, 69

Perhitungan :

Iterasi 4 : AWAL > AKHIR à Rekaman Tidak ditemukan

  1   2     3          4          5      6      7        8       9

Iterasi 4 :  21, 25], [28, 33, 38, 39, 48, 49, 69

Pencarian Interpolasi

Pencarian Interpolasi menentukan posisi yang akan diperbandingkan berikutnya berdasarkan posisi yang diestimasi dari sisa rekaman yang belum diperiksa.

Syarat dalam pencarian berkas dalam pencarian interpolasi adalah kunci rekaman adalah bilangan numeris, karena dalam proses pencarian interpolasi posisi rekaman yang akan dibandingkan dihitung dengan melibatkan proses aritmatik tehadap kunci awal, kunci akhir, dan kunci yang di cari.

Kunci awal adalah kunci awal pada posisi pencarian terakhir, bukan kunci awal berkas.

CONTOH 1

Untuk rekaman dengan susunan sebagai berikut :

   1        2   3       4          5          6         7           8         9

[21, 25, 28, 33, 38, 39, 48, 49, 69]

Berapa probe untuk menentukan rekaman dengan kunci 49 bila menggunakan pencarian interpolasi ?

          1          2   3       4          5          6         7           8         9

Iterasi 1 : [21, 25, 28, 33, 38, 39, 48, 49, 69]

 Iterasi 2 :  21, 25, 28, 33, 38, 39, [48, 49, 69]

Terimakasih untuk para pembaca yang membaca hingga tuntas, saya berharap para pembaca memberi masukan positif dengan cara mengcomment dibawah in, untuk perbaikan isi blog saya kedepannya agar lebih baik lagi. terima kasih sebelumnya

Grammar dan Bahasa(Teori Bahasa&Otomata)

Sebelumnya membahas tentang Pengantar Teori Bahasa&Otomata, kali ini pembahasannya tentang Grammar dan Bahasa..

Simak dan pelajari yahh, semoga membantu

Grammar adalah sebagai kumpulan dari himpunan-himpunan variabel, simbol-simbol 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 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

Dari aturan produksi di atas, menghasilkan suatu variabel a atau variabel ekspresi a+a atau a*a

E à T
T à a

E à T+E
E à a+T
E à a+a

E à T*E
E à a*T
E à a*a

GRAMMAR DAN KLASIFIKASI CHOMSKY

   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 Є VN   : simbol awal (atau simbol start) 

Q  : himpunan produksi

Berdasarkan komposisi bentuk ruas kiri dan ruas kanan produksinya (α → β), Noam 

Chomsky mengklasifikasikan 4 tipe grammar : 

Grammar tipe ke-0 : Unrestricted Grammar (UG) 

Ciri : α, β Є (VT | VN )*, |α|> 0 atau |α|> |β|

Grammar tipe ke-1 : Context Sensitive Grammar (CSG) 

Ciri : α, β Є (VT | VN )*, 0 < |α| ≤ |β|

Grammar tipe ke-2 : Context Free Grammar (CFG) 

Ciri : α Є VN , β Є (VT | VN )* 

Grammar tipe ke-3 : Regular Grammar (RG) 

Ciri : α Є VN , β Є {VT , VTVN} atau α Є VN , β Є {VT, VNVT }

Contoh Analisa Penentuan Type Grammar

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

Jawab :

  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}. 

Jawab :

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}. 

Jawab :

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}. 

Jawab :

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}. 

Jawab :

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

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)

     ¼

   Þ anAan  (2)

   Þ anban  (3)

Dari pola kedua kalimat disimpulkan : 

L1 (G1  ) = { anban ½ n ³ 1}

Tentukan bahasa dari masing-masing gramar berikut :

G2  dengan Q2  = {1. S ® aS,  2. S ® aB,  3. B ® bC,  4. C ® aC,  5. C ® a}.

Jawab :

Derivasi kalimat terpendek : Derivasi kalimat umum :

S Þ aB  (2) S Þ aS  (1)

   Þ abC         (3)     ¼

   Þ aba (5)    Þ an-1S  (1)     

   Þ an B (2)

   Þ anbC   (3)

   Þ anbaC (4)

    ¼

    Þ anbam-1C (4)

    Þ an bam  (5)

Dari pola kedua kalimat disimpulkan : 

L2  (G2 ) = { an bam ½ n ³ 1, m ³ 1}

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

Jawab :

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

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 1: Derivasi kalimat terpendek 3 :

S Þ abC  (2) S Þ aSBC  (1)

   Þ abc (4)         Þ aaSBCBC (1)

Derivasi kalimat terpendek 2 :    Þ aaabCBCBC (2)

S Þ aSBC  (1)    Þ aaabBCCBC (5)

   Þ aabCBC (2)    Þ aaabBCBCC (5)

   Þ aabBCC (5)    Þ aaabBBCCC (5)

   Þ aabbCC (3)    Þ aaabbBCCC (3)

   Þ aabbcC (4)    Þ aaabbbCCC (3)

   Þ aabbcc (6)    Þ aaabbbcCC (4)

   Þ aaabbbccC (6)

   Þ aaabbbccc (6)

Dari pola ketiga kalimat disimpulkan : L 3 (G3 ) = { anbn cn ½ n ³ 1}

Tentukan sebuah grammar regular untuk bahasa L1 = { an | n ≥ 1}

Jawab : 

Q1 (L1 ) = {S → aS | a}
S à a atau
S à aS à aa atau
S à aS à aaS à aaa

Tentukan sebuah grammar bebas konteks untuk bahasa :  

L2 : himpunan bilangan bulat non negatif ganjil

Jawab : 

Langkah kunci : digit terakhir bilangan harus ganjil.  

Buat dua buah himpunan bilangan terpisah : genap (G) dan ganjil (J) 

Q2(L2 ) = {S → J|GS|JS,  G → 0|2|4|6|8,           J → 1|3|5|7|9}

Tentukan sebuah gramar bebas konteks untuk bahasa : 

L3  = 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 

Jawab : 

Langkah kunci : karakter pertama identifier harus huruf.  

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

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

Contoh :

G1 :  VT = {I,  Love, Miss, You}, V = {S,A,B,C}, P = {S ® ABC, A® I, B® Love | Miss, C® You}

S Þ ABC

   Þ I loveYou 

L(G1)={I love You, I Miss You} 

Tentukan apakah produksi-produksi berikut memenuhi aturan grammar Reguler :

A à b
B à bdB
B à C
B à bC
B à Ad
B à bcdef
A à aSa
A à aSS
Ad à dB

Tentukan apakah produksi-produksi berikut memenuhi aturan grammar Bebas Konteks :

A à aSa
B à Ace
B à ab

B à bcdef
B à bcdefG
B à aSS
A à BCDEF
A à AAAA
Ad à dB

Tentukan apakah produksi-produksi berikut memenuhi aturan grammar Konteks Sensitive :

A à bcdefG
B à aSa
B à aSS
B à BCDEF
Ad à dB
ad à b
abC à DE
abcDef à ghijkl
AB à cde
AAA à BBB

Tentukan apakah produksi-produksi berikut memenuhi aturan grammar Unrestricted :

ad à b
abC à DE
AB à cde
ABCDEFG à h
bA à CDEFG

GRAMMAR DAN KLASIFIKASI CHOMSKY LANJT.

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 Î VN  : simbol awal (atau simbol start)

Q : himpunan produksi

HIRARKI CHOMSKY

SEKIAN.