Otomata

Teori Otomata adalah teori mengenai mesin-mesin abstrak, dan berkaitan erat dengan teori bahasa formal. ada beberapa hal yang berkaitan dengan Otomata, yaitu Grammar. Grammar adalah bentuk abstrak yang dapat diterima (accept) untuk membangkitkan suatu kalimat otomata berdasarkan suatu aturan tertentu.
Daftar isi
[sembunyikan]

    * 1 Konsep Dasar
    * 2 Otomata Berhingga
    * 3 Definisi Formal
    * 4 Jenis-jenis Otomata Berhingga
          o 4.1 Otomata Berhingga Deterministik
          o 4.2 Otomata Berhingga Non-Deterministik
          o 4.3 Otomata Pushdown
          o 4.4 Otomata Terbatas Linear
          o 4.5 Mesin Turing
    * 5 Hubungan dengan Tata Bahasa
    * 6 Referensi

[sunting] Konsep Dasar

• Anggota alfabet dinamakan simbol terminal.

• Kalimat adalah deretan hingga simbol-simbol terminal.

• Bahasa adalah himpunan kalimat-kalimat. Anggota bahasa bisa tak hingga kalimat.

• Simbol-simbol berikut adalah simbol terminal :

    * huruf kecil, misalnya : a, b, c
    * simbol operator, misalnya : +, ?, dan *
    * simbol tanda baca, misalnya : (, ), dan ;
    * simbol tanda baca, misalnya : (, ), dan ;
    * string yang tercetak tebal, misalnya : if, then, dan else.


• Simbol-simbol berikut adalah simbol non terminal /Variabel :

    * huruf besar, misalnya : A, B, C
    * huruf S sebagai simbol awal
    * string yang tercetak miring, misalnya : expr

• Huruf yunani melambangkan string yang tersusun atas simbol-simbol terminal atau simbol-simbol non terminal atau campuran keduanya, misalnya : a,ß, dan e

• Sebuah produksi dilambangkan sebagai a --> ß, artinya : dalam sebuah derivasi dapat dilakukan penggantian simbol a dengan simbol ß.

• Derivasi adalah proses pembentukan sebuah kalimat atau sentensial. Sebuah derivasi dilambangkan sebagai : a ==> ß.

• Sentensial adalah string yang tersusun atas simbol-simbol terminal atau simbol-simbol non terminal atau campuran keduanya.

• Kalimat adalah string yang tersusun atas simbol-simbol terminal. Kalimat adalah merupakan sentensial, sebaliknya belum tentu.. Grammar :

Grammar G didefinisikan sebagai pasangan 4 tuple : Vt , Vn , S, dan P, dan dituliskan sebagai G(Vt , Vn , S, P), dimana :

Vt : himpunan simbol-simbol terminal (alfabet) = kamus Vn : himpunan simbol-simbol non terminal S C V : simbol awal (atau simbol start) P : himpunan produksi

Contoh :

1. G1 : VT = {I, want, need, You}, V = {S,A,B,C}, P = {S --> ABC, A--> I, B--> want | need, C--> You}

S --> ABC

  --> IwantYou

L(G1)={IwantYou,IneedYou}

2. . G2 : VT = {a}, V = {S}, P = {S ? aS | a}

S --> aS

 --> aaS
 --> aaa                    L(G2) ={an --> n = 1}

            L(G2)={a, aa, aaa, aaaa,…}

[sunting] Otomata Berhingga
[sunting] Definisi Formal

Otomata adalah sebuah 5-tupel \langle Q, \Sigma, \delta, q_0, F\rangle:

    * Q adalah himpunan berhingga dari state,
    * S adalah himpunan simbol-simbol,
    * d adalah fungsi transisi
    * q_0 \in Q adalah simbol awal
    * F \subset Q adalah state akhir

[sunting] Jenis-jenis Otomata Berhingga
[sunting] Otomata Berhingga Deterministik

Otomata berhingga deterministik (DFA - Deterministic Finite Automata) adalah sebuah otomata yang fungsi transisinya adalah:

    \delta: Q \times \Sigma \rightarrow Q

[sunting] Otomata Berhingga Non-Deterministik

Otomata berhingga non-deterministik (NFA - Nondeterministic Finite Automata) berbeda dengan DFA dalam hal fungsi transisinya:

    \delta: Q \times \Sigma \rightarrow \mathcal{P}(Q)

Fungsi transisi dalam NFA memetakan pasangan Q dan S kepada himpunan kuasa dari Q. Fungsi transisi yang didefinisikan seperti ini memungkinkan suatu simbol masukan untuk mengakibatkan transisi dari sebuah state ke beberapa kemungkinan state yang lain.
[sunting] Otomata Pushdown

Otomata Pushdown adalah salah satu varian otomata dengan 7-tupel \langle Q, \Sigma, \Gamma, \delta, q_0, Z_0, F\rangle, di mana:

    * Q adalah himpunan berhingga dari state,
    * S adalah himpunan simbol-simbol,
    * q_0 \in Q adalah simbol awal
    * F \subset Q adalah state akhir

Ditambah dengan dua unsur, untuk menangani stack:

    * G adalah himpunan berhingga simbol-simbol stack,
    * Z_0 \in \Gamma adalah simbol awal stack,

Dengan fungsi transisinya adalah

    \delta: Q \times (\Sigma \cup \{\epsilon\}) \times \Gamma) \rightarrow Q \times \Gamma^* adalah fungsi transisi

[sunting] Otomata Terbatas Linear
[sunting] Mesin Turing
[sunting] Hubungan dengan Tata Bahasa

Setiap otomata berhingga dapat digunakan untuk mengenali bahasa tertentu.
[sunting] Referensi

    * John E. Hopcroft, Jeffrey D. Ullman - Introduction to Automata Theory, Languages, and Computation

E-to-the-i-pi.svg   Artikel bertopik matematika ini adalah sebuah rintisan. Anda dapat membantu Wikipedia dengan mengembangkannya.

0 Comments:

Post a Comment



ORGANISASI DAN ARSITEKTUR COMPUTER

RAM (Random Access Memory)

Ram adalah singkatan dari Random Access Memory. Sebuah bagian dari system computer yang sangat penting. Tidak hanya pada computer PC maupun notebook saja yang membutuhkan RAM. PDA dan banyak perangkat elektronik lain pun ikut membutuhkan bagiqan ini.

Dan untuk setiap peralatan memiliki tingkat kebutuhan yang berbeda-beda. Misalkan saja sebuah computer yang masih menggunakan operating sdtem lama contohnya window 98. maka RAM yang dibutuhkan tidak akan sebesar computer yang menggunakan windows XP sebagai operating systemnya.

Selain operating system, aplikasi yang dijalankan pun sangat bergantung kepada RAM. Semakin berat aplikasi yang akan dijalankan, maka bobot RAM akan semakin besar. Karena pada RAM-lah untuk sementara aplikasi atau data yang ditengah anda akses tersimpan.

Sedangkan untuk membeli sebuah RAM, bukan bobot saja yang menjadi pertimbangan utama. Tapi juga ada aspek lain yang tidak kalah pentingnya harus ikut difikirkan. Seperti kecepatan tipe, jenis soket, danmotherboad yang digunakan.

Karena saat ini selain setiap aplikasi memiliki kebutuhan system yang berbeda-beda, kehadiran RAM pun sudah sangat beragam. Sedangkan harganya semakin lama semakin terjangkau. Teknologi yang ada pada RAM pun terus berkembang. Mulai ditemukannya DDR, system Dualchenel sampai saat ini sangat baru yaitu DDR2.

Belum lagi kecepataannya yang semakin lama semakin cepat.Dari hanya 66Mhz. begitu pula dengan kapasitas.

Sebelum membahas teknologi yang berkembang pada RAM sendiri, ada baiknya jika terlebih dahulu mengerti apa yang sebenarnya dilakukan oleh RAM dalam system computer sehingga kehadirannya dapat meningkatkan performa sebuah computer.

PENGERTIAN MEMORI

Memory adalah sebuah tempat penyimpanan data dalam sebuah sistem komputer. Memory ada yang bersifat volatile dan ada pula yang bersifat non volatile. Memory yang sifatnya volatile contohnya RAM (Random Access Memory) yaitu memory yang sifatnya menyimpan data sementara selama sistem komputer berjalan, data akan hilang saat computer dimatikan. Sedangkan memory yang sifatnya non volatile atau tetap yaitu memory yang datanya akan tetap ada saat sistem komputer sedang berjalan maupun komputer dimatikan contohnya hardisk, floppydisk, cd-r, dll.
Kapasitas dari memory pun berbeda-beda. Ada yang berkapasitas Megabyte sampai gigabyte. Kapasitas memory dihitung dalam kelipatan 2, yaitu 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, …., 2 pangkat n memory.

Memory 2 k x 8 bit

Terdapa beberapa saluran yang menghubugkan memory dengan prosesor yaitu:

v Saluran data

v Saluran alamat

v Saluran control I/O

v Saluran data

v Saluran awal

v Saluran akhir

Saluran Data

Saluran data adalah saluran yang menghubungkan data pada prosesor dan data pada memory. Banyaknya saluran data tergantung pada banyaknya bit penyimpanan data. Saluran data memberikan lintasan bagi perpindahan data antara dua modul sistem. Saluran-saluran ini secara kolektif disebut bus data. Umumnya saluran data terdiri dari 8, 16, 32 saluran, namun karena perkembangan teknologi yang semakin pesat saat ini sudah ada 64 bit saluran data. Jumlah saluran dikaitkan dengan lebar bus data karena pada suatu saat tertentu masing-masing saluran hanya dapat membawa 1 bit, maka jumlah saluran menentukan jumlah bit yang dapat dipindahkan pada suatu saat. Lebar bus data merupakan faktor penting dalam menentukan kinerja sistem secara keseluruhan. Misalnya, bila bus data lebarnya 8 bit, dan setiap instruksi panjangnya 16 bit, maka CPU harus dua kali mengakses modul memori dalam setiap siklus instruksinya.

Saluran alamat

Saluran alamat adalah saluran yang menghubungkan jumlah alamat pada memory ke prosesor. Banyaknya jumlah saluran alamat tergantung pada kapasitas memory. Saluran alamat digunakan untuk menandakan sumber atau tujuan data pada bus data. Misalnya, bila CPU akan membaca sebuah word (8, 16, atau 32 bit) data dari memori, maka CPU akan menaruh alamat word yang dimaksud pada saluran alamat. Lebar bus alamat menentukan kapasitas memori maksimum. Selain itu, saluran alamat juga menetukan kapasiasitas .

Saluran control I/O


Saluran kontrol digunakan untuk mengontrol akses ke saluran alamat dan penggunaan data pada saluran alamat.. Semua access perpindahan data dari memory ke prosesor dan dari prosesor ke memory diatur / dikontrol di saluran control I/O.

Rangkaian Memory 2 k x 8 bit

2 k x 8 bit = 2048 x 8 bit

= 211 x 8 bit

Saluran Alamat = 11

Saluran Data = 8

Lebar Data = 8

Alamat Awal = 000 0000 00002 = 00016

Alamat Akhir = 111 1111 11112 = 7FF16

Rangkaian Memory 2 k x 8 bit dengan 4 buah Memory 512 x 8 bit (Chip)

512 x 6 bit = 29 x 8 bit

Saluran Alamat = 9

Saluran Data = 8

Lebar Data = 8

Alamat Awal = 0 0000 00002 = 00016

Alamat Akhir = 1 1111 11112 = 1FF16

Berapa buah = 4 Buah

PETA MEMORY

PETA MEMORY
2k x 8 byte

RANGKAIAN MEMORY RAM

RANGKAIAN MEMORY RAM
MEMORY 2k x 8byte