MENGUBAH NFA  DENGAN  Ɛ - MOVE KE NFA TANPA  Ɛ - MOVE NFA dengan  Ɛ -move ( NFA  Ɛ -move ) Disini kita mempunyai jenis otomata baru yang disebut NFA dengan   Ɛ -move( Ɛ  disini bisa dianggap sebagai empty). Pada NFA dengan  Ɛ -move (transisi  Ɛ ), diperbolehkan merubah state tanpa membaca input. Disebut dengan transisi  Ɛ  karena tidak bergantung pada suatu input ketika melakukan transisi. Contoh: Mesin NFA dengan  Ɛ -move

EKIVALENSI NON-DETERMINISTIC FINITE AUTOMATA KE DETERMINISTIC FINITE AUTOMATA Dari sebuah mesin NFA dapat dibuat mesin DFA-nya yang ekivalen (bersesuaian). Ekivalen disini artinya mampu menerima bahasa yang sama. Lihat FSA pada gambar 1 dan gambar 2. Gambar 1 adalah DFA sedangkan gambar 2 adalah NFA. Meskipun yang satu DFA dan yang lainnya NFA, kedua-duanya menerima bahasa yang sama, yang dalam ekspresi regular = 0 (0 U 1)* GB 1. Mesin DFA

PENDAHULUAN Teori Bahasa dan Otomata Teori bahasa dan otomata merupakan bagian dari teori komputasi pada ilmu komputer. Beberapa teori komputasi datang dari bahasa dan rekayasa sistem, terutama yang berbasiskan matematika. Dalam hal ini penekanannya adalah pada pemecahan masalah. Melalui contoh-contoh ilustrasi-masalah dapat dikenali latar belakang dari suatu konsep dan hubungannya dengan definis dan teorema yang ada. Secara teoritis ilmu komputer diawali dari sejumlah berbeda disiplin ilmu; ahli biologi mempelajari neural network, insinyur elektro mengembangkan switching sebagai tools untuk mendesain perangkat keras, matematikawan bekerja berdasarkan logika, dan ahli bahasa menyelidiki tata bahasa untuk bahasa alami (natural language) Finite state automata dan ekspresi reguler awal dikembangkan berdasarkan pemikiran neural network dan switching circuit. Finite state automata merupakan tools yang sangat berguna dalam per...