TEORI BAHASA DAN AUTOMATA

Ilmu komputer memiliki dua komponen utama:

1.    Model dan gagasan mendasar mengenai komputasi,

2.    Teknik rekayasa untuk perancangan sistem komputasi, meliputi perangkat keras dan perangkat lunak, khususnya penerapan rancangan dari teori. Sedangkan Teori bahasa dan automata merupakan bagian pertama

Algoritma adalah langkah-langkah untuk menjelaskan sesuatu masalah yang pasti dan mempunyai hasil.

Semi algorima adalah suatu prosedure yang bersifat bahwa dia tidak dapat berhenti baik jawaban ada  atau tidak ada.

10. Input A

20. x = 1

30. y = x * x

40. if y = A then print x:end;

45. if y > A then end

50. y = x + 1

Suatu bahasa pemprograman harus didefinisikan secra spesifikasi dari sebuah bahasa pemprograman meliputi hal-hal berikut:

§  Himpunan simbol-simbol (alphabet) yang bisa dipakai untuk menbentuk program yang benar.

§  Himpunan pemprograman yang benar secara sintaktik

§  Makna dari pemprograman tersebut.

Secara teoritis ilmu komputer diawali dari sejumlah berbeda disiplin ilmu: ahli biologi mempelajari neural network, insinyur elektro , mengembangkan switching sebagai tool untuk mendisain hardware, matematikawan bekerja mendasarkan logika, dan ahli bahasa menyelidiki tata bahasa untuk neural language.

Automata

Adalah himpunan hingga simbol-simbol variable-variable dan presedure secara automatis menentukan apakah suatu untai diterima atau ditolak.

Huruf dan digit adalah contoh dari simbol yang sering dipakai. Sebuah string (kata/untai) adalah suatu deretan berhingga dari simbol-simbol.

Sebagai contoh, ‘a’, ‘b’, ‘c’, adalah simbol-simbol, dan ‘abcb’ adalah suatu string. Dan panjang string adalah jumlah simbol yang membentuk string tersebut.

‘abad’ panjang string 4

‘asdfgh’ panjang string 6

Kemudian automata juga merupakan suatu mesin yang menghasilkan bahasa komputer.

Automata dibagi menjadi 2 :

1.    Automata Hingga (AH) / Finite state Automata ( FSA )

Adalah model matematika dari sebuah sistem dimana input dan outputnya dalah diskrit (bernilai) bisa diterima atau ditolak. AH dipergunakan untuk bahasa legurel, dan AH dibagi menjadi 3 yaitu:

a)    AH Deterministik (AHD) / Deterministik Finite Automata DFA

Adalah AH yang didefinisikan menjadi 5 tupel :

1.    Himpunan hingga internal stat (s)

{ Q₀, Q₁, …, Q_~ }

2.    Himpunan hingga simbol (v)

{ a, b, c, … , z }

3.    State awal

(Q₀ Є s)

4.    Himpunan hingga statement rima ( ζ )

5.    Sebuah fungsi f:sxv Ù s

Algorima moore adalah algoritma untuk menetapkan apakah 2 Automata Hingga Deterministik ekuivalen.

b)   AH Non Deterministik / Non deterministik finite Automata NFA

Mempunyai transisi lebih dari satu strata

c)    AH Non deterministik dengan transisi rantai hampa / Transisi NFA

b) dan c) sering disebut sebagai graftransisi.

2.    PUSH DOWN AUTOMATA

Adalah automata hingga yang dilengkapi dengan input tape dan push down stack.

Push down stack adalah suatu tempat penyimpanan huruf input sampai dibutuhkan kembali.

Automata push down dipakai untuk mengenali jenis bahasa conteks free. Automata push down termasuk termasuk automata hingga pada push down automata dilengkapi input tape dan push down stack.

GRAMMAR

Secara umum grammar adalah suatu sistem matematis untuk mendefinisikan bahasa.

Suatu cara untuk memberikan struktur pada kalimat dalam suatu bahasa.

Dalam Automata grammar koleksi dari variable non terminal dari variable non terminal (V_n/N), variable terminal (V_t/T), simbol stat (S), Produksi (P/Q).\

Jadi Grammar G (V_n, V_t, S, P)

Dimana :

V_N         : himpunan simbol non terminal (kelas sintaks) , huruf

                kapital

V_T                    : himpunan simbol terminal, huruf  kecil

S       : suatu simbol tertentu dari V_N, yang disebut dengan simbol Start , S Î V_N

P       : adalah sub himpunan hingga yang tidak kosong dari relasi , aturan produksi

Bahasa adalah himpunan semua kata-kata dengan panjang berhingga yang berbentuk atas sejumlah hingga alfabet / simbol-simbol terminal (V_T) yang memenuhi aturan P

Metode untuk menyatakan bahwa bahasa dibagi menjadi 2 :

1.    Metode sistem generatif disebut grammar.

Adalah setiap kalimat yang terbentuk dalam bahasa, menggunakan aturan-aturan produksi-produksi grammar.

2.    Metode dengan menggunakan mesin abstrak disebut ACCEPTOR atau penerima.

Mesin ini berfungsi untuk menentukan apakah suatu kalimat adalah suatu bahasa.

Vacabulary adalah himpunan yang terdiri dari simbol-simbol terminal suatu grammar. = V_T*

G =  (V_n, V_t, S, P)

Contoh grammar :

G=( { A,S } , { 0,1 } ,  S , P )

        

           V_n          V_T        S      P

Klasifikasi Grammar :

Didasarkan format-format dari produksi-produksinya menurut chomsky dibagi menjadi 4 :

1.    Tipe Nol (0) à tipe tidak dibatasi

Format-format produksinya bebas

§  α à β

§

Contoh  :

s à CD                -------- ok

aAD à aD         -------- ok

2.    Tipe Satu (1) (Context Sensitive Grammar, CSG)

Adalah grammar pembatas didalam produksi

Syarat umum:

§  α à β

§  |α| ≤ |β|

§  α ,β Î (V_N È V_T )* --------bisa gabung V_N or V_T

Contoh :

Sabc à aSBC     -------- Jumlah kiri £ kanan

S à abc              -------- Ruas kiri dan kanan bisa V_N, V_T atau

   kedua-duanya (bebas)

3.    Tipe Dua (Context Free Grammar, CFG)

Syarat umum:

§  α à β

§  |α| ≤ |β|

§  S ruas sebelah kiri harus 1

§  β  Î (V_N È V_T )*, à bebas                                   

§  α ε Vn                                       

          Contoh :

          S àaA

          A à aAB

          B à b

4.    Tipe tiga(3) Reguler Grammar ( RG)

§  α à β

§  |α| ≤ |β|

β à aB | a                β, B ε V_n

                                  a ε V_t*

Contoh:

S à B                                S àa

A à aB                             C àc