TEORI BAHASA AUTOMATA

A. TEORI BAHASA

Teori bahasa membicarakan bahasa formal, terutama untuk kepentingan perancangan kompilator dan pemroses naskah. Bahasa formal adalah kumpulan kalimat dalam sebuah bahasa yang dibangkitkan oleh sebuah tata bahasa yang sama.


B. AUTOMATA

Automata adalah mesin abstrak yang dapat mengenali,menerima, dan membangkitkan sebuah kalimat dalam bahasa tertentu.
Automata merupakan suatu sistem yang terdiri atas sejumlah berhingga state, dimana state menyatakan informasi mengenai input yang lalu dan dapat dianggap sebagai memori mesin. Input pada mesin automata dianggap sebagai bahasa yang harus dikenali oleh mesin. Selanjutnya, mesin automata membuat keputusan yang mengindikasikan apakah input itu diterima atau tidak.


C. FINITE STATE AUTOMATA

Finite State Automata (FSA) merupakan mesin automata dari bahasa reguler.
FSA memiliki state yang banyaknya berhingga dan dapat berpindah – pindah dari satu state ke state yang lain. Perpindahan state dinyatakan dengan transisi.
FSA dapat menerima input & menghasilkan output.

  • Lingkaran menyatakan state/ kedudukan
  • Lingkaran ganda menyatakan state akhir ( final state )
  • Label pada lingkaran adalah nama state tersebut
  • Busur menyatakan transisi / perpindahan state
  • Label pada busur adalah simbol input
  • Lingkaran didahului oleh sebuah busur tanpa label menyatakan state  awal
  • Simbol input { 0.1}
  • State awal Even
  • State akhir Odd

Secara formal Finite State Automata dinyatakan dengan 5 tuple:
            Q = Himpunan state atau kedudukan
            S = Himpunan simbol input / masukan / abjad / angka
            d = Fungsi transisi
            S = State awal / kedudukan awal, S € Q
            F = Himpunan state akhir, F € Q


D.  JENIS-JENIS FSA
 
1. Mesin DFA (Deterministic Finite Automata)
Dimana:
Q = {q0, q1, q2}
S = {a, b }
S = {q0}
F = {q2}

Fungsi Transisi                                   
 d ( q0, a ) = qo                                               
 d ( qo, b ) = q1
 d ( q1, a ) = q1
 d ( q1, b ) = q2
 d ( q2, a ) = q1
 d ( q2, b ) = q2

Tabel Transisi
d
a
b
q0
q0
q1
q1
q1
q2
q2
q1
q2



     2.    Mesin NFA (Non-deterministic Finite Automata)

Dimana:
Q = { q0, q1 }                                                      
S = { a, b }                                   
S = { q0 }                         
F = { q1 }                         

Fungsi Transisi:
d { q0, a } = q1
d { q0, b } = f
d { q1, a } = q1
d { q1, b } = q0

Tabel transisi
d
a
b
q0
q1
f
q1
q1
q0


 
E. EKIVALENSI NFA KE DFA

Dari sebuah mesin NFA dapat dibuat mesin DFA yang ekivalen.
Ekivalen artinya mampu menerima bahasa yang sama .
·        Suatu DFA dapat dipandang sebagai kasus khusus (subset) dari NFA.
·        Jelas bahwa kelas bahasa yang diterima oleh DFA juga akan diterima oleh DFA
·        Namun ternyata DFA juga dapat mensimulasikan  NFA; yaitu untuk setiap NFA kita dapat membuat  DFA yang ekivalen
·        Dapat dibuktikan bahwa DFA dan NFA adalah  ekivalen, sehingga dapat disebut FA saja

Contoh:


f = ( { q0 }, { q1} )
S = { 0, 1 }
S = q0
F = q1

Tabel Transisi
d
0
1
q0
{ q0, q1 }
q1
q1
f
{ q0, q1 }

Telusuri setiap state yang ada dimulai dari { q0 } :
Ø   State { q0 } bila memperoleh input o menjadi state { q0, q1 }
Ø   State { q0 } bila memperoleh input 1 menjadi state { q1 }



Ø  State { q1 }
    - State { q1 } bila memperoleh input o menjadi state f
    - State { q1 } bila memperoleh input 1 menjadi state { q0, q1 }
Ø   State { q0, q1 } bila memperoleh input o menjadi state { q0, q1 }
    diperoleh dari d ( q0, 0 ) = { q0, q1 }    d ({ q0, q1}, 0) = { q0, q1 }
                           d ( q1, 0 ) = f
Ø   State { q0, q1 } bila memperoleh input 1 menjadi { q0, q1 }
    diporoleh dari d ( q0, 1 ) = { q1 }  
                        d ( q1, 1 ) = { q0, q1 }
                        d ({ q0, q1 }, 1) = { q0, q1}

Hasil setelah penelusuran { q1 }, { q0 }, { q0, q1 }

Konfigurasi Mesin
Q = ( qo, { q0, q1 }, q1, f )
e = { 1,0 }
S = q0
F = ( q1, { q0, q3 } )

Tabel Transisi
d
0
1
q0
{ q0, q1 }
q1
q1
f
{ q0, q1 }
{ q0, q1 }
{ q0, q1 }
{ q0, q1 }
f
f
f

Comments

Post a Comment

Popular posts from this blog

MESIN MOORE DAN MESIN MEALY

Image
MESIN MOORE Mesin moore adalah finite-state machine yang nilai outputnya ditentukan berdasarkan statenya. Mesin Moore dinamai Edward F. Moore , yang mempresentasikan konsep itu dalam sebuah makalah tahun 1956, " Gedanken-experiments on Sequential Machines" Diagram Mesin Moore atau Diagram Moore adalah diagram yang menghubungkan nilai output dengan masing-masing state.   Mesin moore ditetapkan ke dalam 6 tuple yang terdiri dari:  -   Himpunan State (S)    -   State awal  ( S 0 )    -   Himpunan input  ( ∑)    -   Himpunan output  ( ꓥ)    -   Fungsi Transisi (T )    -   Fungsi output (G )   Contoh Mesin Moore: MESIN MEALY Mesin Mealy adalah finite-state machine yang nilai outputnya ditentukan oleh state dan inputnya. Mesin Mealy adalah deterministic finite-state transducer , untuk setiap k...
Read more

BENTUK NORMAL CHOMSKY

BENTUK NORMAL CHOMSKY Bentuk normal Chomsky / Chomsky Normal Form (CNF) merupakan salah satu bentuk normal yang sangat berguna untuk tata bahasa bebas konteks. Bentuk normal Chomsky dapat dibuat dari sebuah tata bahasa bebas konteks yang telah mengalami penyederhanaan yaitu penghilangan produksi useless, unit, dan ε. Dengan kata lain, suatu tata bahasa bebas konteks dapat dibuat menjadi bentuk normal Chomsky dengan syarat tata bahasa bebas konteks tersebut: 1.          Tidak memiliki produksi useless 2.          Tidak memiliki produksi unit 3.          Tidak memiliki produksi ε Aturan produksi dalam bentuk normal Chomsky ruas kanannya tepat berupa sebuah terminal atau dua variabel. Misalkan: A -> BC A -> b B -> a C -> BA | d Pembentukan Bentuk Normal Chomsky   Langkah-langkah pembentukan   bentuk normal C...
Read more

MESIN TURING

Image
MESIN TURING Mesin Turing adalah model komputasi teoretis yang ditemukan oleh Alan Turing , berfungsi sebagai model ideal untuk melakukan perhitungan matematis. Walaupun model ideal ini diperkenalkan sebelum komputer nyata dibangun, model ini tetap diterima kalangan ilmu komputer sebagai model komputer yang sesuai untuk menentukan apakah suatu fungsi dapat selesaikan oleh komputer atau tidak Mesin turing mempunyai 7 Tuple             M = (Q, å , G , d , S, F, q )             Q          = himpunan state             å          = Himpunan simbol input             G           = simbol pada pita      ...
Read more