Mengenal Teori Bahasa dan Automata …

          Teori bahasa dan automata merupakan salahsatu komponen ilmu informatika, teori ini merupakan ide dan model fundamental yang mendasari sebuah system komputasi, teori ini juga bisa disebut sebagai sebuah teknik rekayasa untuk perancangan system komputasi.

          Beberapa bidang ilmu lain yang mendukung pengembangan metode komputasi :

1.     Biologi

Mempelajari jaringan neuron yang mengilhami ditemukanannya finite automata.

 

2.     Rangkaian Elektronika

Mempelajari teori switching sebagai perancangan perangkat keras menggunakan finite automata.

 

3.     Matematika

Mengembangkan system logika yang berguna untuk masalah pembuktian automata.

 

          Beberapa model komputasi dalam automata:

 

1.     Finite automata (FA)

Sering juga disebut dengan Finite State Automata (FSA). Terdiri dari Deterministic Finite Automata (DFA) dan Non Deterministik Finite Automata (NDFA). Teori dasar dari FA sangat umum yaitu system pada saat berada di salahsatu state dari sejumlah state bergerak diantara state-state secara dapat diproduksi yang bergantung pada masukan ke system. Salah satu penerapannya adalah kompilasi/translasi bahasa pemograman tingkat tinggi menjadi bahasa mesin yang ekivalen. Finite automata merupakan jenis otomata yang tidak memiliki memori sementara, FA adalah kelas mesin dengan kemampuan paling terbatas.   

 

2.     Pushdown Automata (PA)

Terdiri dari Deterministic Pushdown Automata (DFA) dan Non Deterministik Pushdown Automata (NDFA). PA memiliki memori sementara dengan mekanisme stack LIFO (Last In First Out).

 

3.     Turing Machine (TM).

Memiliki mekanisme Random Access Memory.

Dalam teori bahasa dan Automata digunakan model state (State Machine Model). atau biasa disebut model transisi (State Transition Model), pengembangan teori automata difasilitasi dengan perkembangan bidang Psycho Linguistik.

 

    Beberapa terminologi dasar dari sebuah teori bahasa diantaranya:

          Alphabet

          Concatination / penyambungan

          String

 

Dalam teori bahasa, Istilah huruf = karakter = simbol dan istilah kalimat = kata = string.

 

·        Simbol / huruf / karakter

Merupakan sebuah elemen alphabet yang memiliki makna unik / tunggal, misalnya symbol A dan symbol B yang memiliki makna berbeda.

·        Alphabet

Dilambangkan dengan huruf capital miring, alphabet adalah himpunan tak kosong yang berhingga dari symbol – symbol.

·        Kata / kalimat / String

Kata merupakan dereten symbol –simbol dari suatu alphabet

 

Contoh :

 

            C = {a,b,c,1,2,3}

 

o       Contoh diatas merupakan contoh sebuah alphabet C yang memiliki 6 buah symbol

o       Contoh sebuah kata / string dari alphabet C: acca, back, 132, a12, dst.

o       Kata acca dengan  caac memiliki makna yang berbeda.

o       Kata acca, 121, abba memenuhi aturan palindrome (walaupun kata dibalik memiliki makna yang sama).

 

Operasi dalam teori bahasa

 

·        Panjang kata

Jika x sebuah kata, maka panjang kata x dilambangkan dengan |x| yang menunjukan jumlah imbol yang membentuk kata x.

 

Contoh : jika x = abc, maka panjang kata x = |x| = 3

 

            Panjang dari sebuah kata kosong adalah 0, yang dinotasikan dengan ε.

 

·        Concatenation / penyambungan

Jika x dan y dua buah kata, maka concatenation : x o y atau xy,

 

Contoh : x = accd , y = bbaa maka x o y = accdbbaa (sampai disini mudah bukan J)

 

·        Beberapa aturan kata / string pada suatu alphabet

o       V = {‘p’,’q’,’r’,’s’} berbeda dengan V = {p,q,r,s,}

o       Vn = V o V o V o V…. o V sebanyak n kali.

Atau

Vn = V V V V…. V sebanyak n kali

o       V+ = V1  U V2 U V3 U …

o       V* = {ε} U V+. yang juga berarti V* = {ε} U V1 U V2 U V3 U …

o       ε merupakan sring kosong dan memiliki sifat identitas.

o       Sebuah bahasa merupakan himpunan string pada V, missal: bahasa G = L(G)

·        Pencerminan

Jika X sebuah kata maka pencerminan X dilambangkan dengan X-1

 

            Contoh: x = akar, maka x-1 = raka

 

·        Pengulangan

 

Contoh: x = rindu, maka pengulangan: x = xn

 

x= ε

x1 = rindu

x2 = rindurindu

x3 = rindurindurindu

dst…

 

 

 

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s