SIMULATOR PENGENAL STRING YANG DITERIMA SEBUAH DETERMINISTIC FINITE AUTOMATA (DFA)

SUPARYANTO, Selo, S.T., M.T., M.SC., P.Hd.

2017 | Tesis | S2 Teknik Elektro

Untuk mempermudah dalam mengenali dan membangkitkan bahasa sederhana yang termasuk dalam kelas Regular Language, dan untuk membantu mempelajari teori bahasa dan automata bisa dipergunakan sebuah simulator, Simulator Deterministic Finite Automata adalah sebuah perangkat yang bisa dipergunakan untuk melakukan pengecekan terhadap inputan-inputan string pada sebuah Deterministic Finite Automata (DFA) sebelum sebuah string dimasukkan kedalam sebuah DFA. Simulator DFA ini dibuat dengan beberapa tahapan, tahap pertama, ditentukan terlebih dahulu sebuah diagram transisi mesin DFA dengan sejumlah state, tahap kedua, dibuat konfigurasi mesin DFA dan tabel transisinya, dari diagram dan tabel transisi tersebut selanjutnya dibuat algoritma dengan menggunakan tipe data enumerasi. Tahap ketiga, dibuat algoritma untuk menginputkan dan melakukan pengecekan string yang dimasukkan kedalam simulator tersebut, dengan memperhatikan state awal dan state akhirnya. Pembacaan string dimulai dari state awal, ditelusuri karakter perkarakter dari string yang dibaca, dicocokkan dengan input yang di terima pada setiap state. Tahap keempat, menentukan output dari hasil pembacaan string oleh mesin DFA, apabila karakter yang dibaca tidak berakhir di state akhir, berarti output yang dihasilkan string tersebut tidak diterima oleh DFA, sebaliknya jika penelusuran berakhir di state akhir, maka output yang dihasilkan string yang dibaca tersebut diterima oleh DFA. Untuk mengetahui efektivitas dan efisiensi waktu dari algoritma yang dibuat, selanjutnya dilakukan analisis algoritma dengan cara menentukan kompleksitas waktu algoritma. Dengan analisis algoritma ini akan diketahui kemangkusan algoritma, yang diukur dari berapa jumlah waktu dan ruang memori yang dibutuhkan untuk menjalankan algoritma tersebut.

To make it easier to recognize and generate simple languages included in the Regular Language classes, and to help learn the theories of language and automata can be used a simulator, the Deterministic Finite Automata Simulator is a device that can be used to check the string inputs in a Deterministic Finite Automata (DFA) before a string is entered into a DFA. DFA simulator is made with several stages, the first stage, is determined first a DFA machine transition diagram with a number of states, the second stage, the configuration of DFA engine and transition table, from the diagram and transition table is then created algorithm using enumeration data type. The third stage, created an algorithm to input and check the string entered into the simulator, with respect to the initial state and the final state. String readings start from the initial state, character traced characters from the read string, matched with input received at each state. The fourth stage, determining the output of a string reading by a DFA machine, if the read character does not end in the final state, it means that the output produced by the string is not accepted by the DFA, otherwise if the search ends in the final state, the resulting output of the read string Accepted by DFA. To know the effectiveness and time efficiency of the algorithm made, then performed algorithm analysis by determining the time complexity of the algorithm. With this algorithm analysis we will know the algorithm's capability, as measured by the amount of time and memory space needed to run the algorithm.

Kata Kunci : Simulator, DFA, diagram transisi, tabel transisi, algoritma, state, state awal, state akhir, string, kompleksitas algoritma, mangkus