Teori Bahasa dan Automata - Pengantar

Automata : abstract computing devices, mesin abstrak yang dapat mengenali (recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu.

Teori bahasa membicarakan bahasa formal (formal language).
Bahasa formal adalah sebuah kalimat. Sebuah kalimat dalam sebuah bahasa dibentuk/generate oleh sebuah tata bahasa (grammar) yang sama.
Dikatakan bahasa formal karena grammar diciptakan mendahului pembentukan setiap kalimatnya. Sebuah bahasa formal bisa dibangkitkan oleh dua atau lebih tata bahasa yang berbeda.

Mengapa mempelajari?
Finite automata merupakan suatu model yang sangat bermanfaat, berikut beberapa contoh bagaimana bahasa ini digunakan:
1. Software untuk perancangan dan pemeriksaan perilaku sirkuit digital.
2. Lexical analyzer sebuah compiler, yang merupakan komponen dari ccompiler yangmembagi / memecah teks input menjadi beberapa unit logikal seperti identifier, keyword maupun tanda baca.
3. Software untuk pencarian urutan kata

Contoh sederhana:
Pemodelan finite automata untuk switch on/off:

           START STATE  (1)          FINAL STATE (>=1)
                              Qo                                   Q1

Pemodelan finite automata sebagai bagian dari lexical analyzer parser:

String, alphabet and language
Simbol: merupakan sebuah entitas abstrak (tidak mempunyai arti bila berdiri sendiri). Dikenal dengan uninterpreted
Contoh:
   Huruf A-Z, a-z
   Digit: 0-9
   Special Characters: $, =,(, dst

Alfabet: merupakan himpunan berhingga (finite set) dari simbil-simbol, dinotasikan dengan sigma.
Contoh:
   sigma1 = {a,b,..,z}
   sigma2 = {0,1}

String: merupakan deret terbatas dari simbol-simbol yang ada dalam alfabet.
Contoh: jika a,b dan c adalah alfabet maka string yang bisa dibentuk: abcb, aab, bca
String hampa (dinyatakan dengan epsilon atau ^) = string yang tidak memiliki simbol. String hampa dapat dipandang sebagai simbol hampa.
Panjang string dinotasikan dengan |   |
Contoh:
   w = "makan"
   |w| = 5
   w = epsilon
   |w| = 0

Language: himpunan string dari alfabet
- Ada 2 macam: finite dan infinite language
  Contoh Finite Language: {a,ab,abb}
  Contoh Infinite Language: himpunan palindrome atas sigma = {0,1} ->hasilnya tak berhingga banyaknya

- Language Concatenation: penyambungan dua buah string
   Contoh:
      P, Q = Language
      P.Q = konkatenasi P dan Q
      P = {0, 1, 00, 01, 10}
      Q = { 10, 11 }
      PQ = {010, 011, 110, 111, 0010, 0011, 0110, 0111, 1010, 1011}

- Union Language: penggabungan dua buah string
      *anggep aja u = simbol union
      P u Q = Union P dan Q
      P = {0, 1, 00, 01, 10}
      Q = { 10, 11 }
      P u Q = {0, 1, 00, 01, 10, 11}

- Closure Language
   Kleene Closure ( * ) = konkatenasi string yang sama yang diberi tanda *.
 

  Positive Closure = konkatenasi string yang sama minimal satu kali

  Perbedaan kurung dan tidak

  (1100)* = { epsilon ,1100, 11001100, 110011001100, ...}

  1100* = { 110epsilon, 1100, 11000, 110000, ... }