Automata

1. Jelaskan apa yang dimaksud dengan Otomata dan Finite Automata (otomata berhingga)!

Otomata adalah mesin abstrak yang menggunakan model matematika, tetapi matematika yang digunakan benar-benar berbeda dibanding matematika klasik dan kalkulus. Model yang digunakan adalah model mesin state (state machine model) atau model transisi state (state transition model).
Finite Automata (otomata berhingga) adalah mesin abstrak berupa sistem model matematika dengan masukan dan keluaran diskrit yang dapat mengenali bahasa paling sederhana (bahasa reguler) dan dapat diimplementasikan secara nyata dimana sistem dapat berada disalah satu dari sejumlah berhingga konfigurasi internal disebut state.

2. Jelaskan apa yang di maksud dengan Regular Expresion (RE) !

• Bahasa regular dapat dinyatakan sebagai ekspresi regular dengan menggunakan 3 operator : concate, alternate, dan closure.
• Dua buah ekspresi regular adalah ekuivalen jika keduanya menyatakan bahasa yang sama

3. Diketahui Grammar, dengan himpunan simbol terminal { a, b} dan produksi sebagai berikut ( huruf kecil menyatakan simbol terminal )

S a

S Sa

S b

S bS

Jelaskan bagaimana bentuk umum dari untai yang dibentuk oleh Grammar tersebut.

Grammar diatas terdiri dari produksi berbentuk :

a ß dengan ¦a¦ ¦ß¦. Dimana a ialah string dan ¦a¦ ialah panjang dari string a demikian juga ß ialah string dan¦ß¦ ialah panjang dari string ß. String disini adalah merupakan deretan simbol baik terminal maupun non terminal.

4. Buatlah pohon derivasi untuk ekspresi bentuk berikut :

• ( x – y * 2 + z ) div ( x div z )
• a * ( 2 * c – b ) * 2
• x * ( y – 5 ) * ( y div 4 + x )
• ( x * 2 * y ) – ( ( z + 32 ) div y )

( x – y * 2 + z ) div ( x div z )

a * ( 2 * c – b ) * 2

x * ( y – 5 ) * ( y div 4 + x )

( x * 2 * y ) – ( ( z + 32 ) div y )

Posted in: Virlab