Teori Bahasa dan Automata - Soal Kuis

SOAL KUIS

1. RE = (a+b)^+  a*b
    a. Buat Transition Diagram menggunakan epsilon-NFA !
    b. Buat E-closurenya untuk menentukan DFA ekivalen!
    c. Minimalisasi DFA tersebut!

2. Buatlah minimalisasi dari NFA berikut

3. Buatlah RE dari FSA dibawah ini!

Read More

Teori Bahasa dan Automata - Konversi DFA ke CFG

Tatabahasa Linier

G = ( V, T, P, S )
Dimana V = Variabel yang digunakan
              T = Input yang ada

1. Konversi FSA -> CFG
    Aturan pengubahan:
    - setiap transisi status d(A, a) = B diubah menjadi aturan produksi A -> aB
    - Setiap final state P diubah bentuknya menjadi aturan produksi P -> epsilon
DFA

Tatabahasa Linier untuk FSA diatas adalah
G = ( {S, S1, S2, S3} , {a, b}, P, S )
dengan aturan produksi P:
S -> S1
S1 -> aS2
S2 -> bS3
S3 -> epsilon

NFA

Tatabahasa Linier untuk FSA diatas adalah
G = ( {L1,L2,L3} , {a,b,c}, P, S )
dengan aturan produksi P:
L1 -> aL2 | bL3
L2 -> aL3 | bL1 | bL2
L3 -> aL3 | bL3 | cL1 | bL2 | epsilon

2. Konversi RE ke CFG
Aturan:

Contoh: Diketahui RE = ( 01* | a )* b ( 01 | 10 )? b
CFG =
***PERMISALAN: A = (01* | a)* ; B = b; C = (01 | 10)? ; D = b
      E = 01* | a ; F = 1* ; G = 01 | 10;
***HINT = R? -> R + epsilon

S -> A B C D
A -> EA | epsilon
E -> 0F | a
F -> 1F | epsilon
B -> b
C -> G + epsilon
G -> 01 | 10
D -> b

atau B dan D dihilangkan, menjadi
S -> A b C b (b tidak dimisalkan lagi)

Read More

Teori Bahasa dan Automata - Minimalisasi DFA

INGAT ! yang bisa diminimalisasi hanya bentuk DFA. Jikalau masih dalam bentuk NFA ubahlah ke bentuk DFA dahulu (DFA Ekivalen)

Contoh: Diketahui DFA

Minimalisasi:
1. Pisahkan Non - Final State dan Final State

   Non - FinalState              FinalState
        1, 3                                   2

2. Masukkan input ke setiap state seperti dibawah, jika ada lebih dari 1 state yang mengarah ke state yang sama jika diberi input yang sama, maka dikatakan indistinguishable.

Non-Final State

 -> State 1 dan 3 dikatakan indistinguishable karena jika diberi input a dan b akan mengarah ke state yang sama

Final State







3. Buat tabel Minimalisasi
Caranya: Buat tabel dengan kolom sesuai jumlah state-1 dan Baris sejumlah state-1. Beri tanda X jika pasangan state tidak sama (distinguishable) dan tanda O bila pasangan state ekivalen (indistinguishable)

4. Buat transition diagramnya
Transition Diagram yang diminimalisasi:

Contoh Latihan soal yang lebih rumit (dari slide, silahkan pelajari sendiri dari penjellasan yang sudah diberikan)

Read More

Teori Bahasa dan Automata - Epsilon-NFA

Finite Automata dengan Epsilon Transition: memungkinkan adanya transisi antara input kosong (empty) dari state Q.

Menggunakan Algoritma Thompson:

Contoh Soal:
Diketahui RE = (a+b)*abb
1. Buat Transition Diagramnya! (dengan algoritma Thompson)
2. Buat DFA-Ekivalennya!

1. Transition diagram:

2. DFA Ekivalen
*anggeplah E = lambang epsilon
E-closure -> sampai state berapa bisa tersambung dengan epsilon

Transition Diagram DFA Ekivalen:

State Table:

YANG PERLU DIINGAT !
RE = (a+b)*abb
Transition diagram:

RE = a(a+b)abb
Transition Diagram:

*Input epsilon setelah q0 dan setelah q6 HANYA dikarenakan ada tanda * setelah (a+b). Jika tidak, maka tidak perlu diberi input epsilon terlebih dahulu.

Read More

Teori Bahasa dan Automata - Finite Automata

Sistem Finite State:
- Deterministic Finite Automata (DFA)
- Non-Deterministic Finite Automata (NFA)
- Push-Down Automata (PDA)
- Turing Machine
- Linear Bounded Automata

DFA
- Tiap inputan akan mengarah ke satu tujuan yang pasti, antara ke state lain atau ke diri sendiri
contoh = Diketahui Transition Diagram:

Untuk menuju Final state (Q1), Jalur yang dapat ditempuh adalah:
1. Q0 diberi input 0 ke Q1
2. Q0 diberi inputan 1 ke Q2, Q2 diberi input 1 ke Q1

Definisi formal:

Dimana dari Transition Diagram diatas, definisi formalnya menjadi:
Q = {Q0,Q1,Q2}
sigma = {0,1}
F = {Q1}

Fungsi Transisi dapat dibuat melalui Tabel Transisi:

            |       Input
   State  |   0      |      1
______ |_____|______
  ->Q0     |    Q1   |   Q2
    *Q1     |    Q1   |   Q1
     Q2     |    Q2  |   Q1

-> untuk Start State
* untuk Final State

Input yang Benar (berdasarkan transisi diagram):
- 00
- 1001
- 111

Input yang Salah:
- 001
- 100

Syarat String diterima sebagai bahasa dalan Finite State Automata (FSA)
1. Input String habis terbaca, DAN
2. State berpindah dari start state dan berhenti pada final state

Penelusuran String yang diterima (berdasarkan transition diagram)
Misalkan string "001"

NFA

- Tiap input dapat mengarah ke lebih dari satu state berbeda

Contoh: Tabel Transisi NFA

Definisi formal: ( {Q0,Q1,Q2,Q3,Q4}, {0,1},    , Q0, {Q2, Q4} )

Tabel Transisi
            |       Input
   State  |   0      |      1
______ |_____|______
  ->Q0     | {Q0,Q3} |   {Q0,Q1}
     Q1      |            |   Q2
    *Q2     |    Q2    |   Q2
     Q3     |     Q4   |
    *Q4     |      Q4  |  Q4

Konversi NFA ke DFA Ekuivalen

Transition Diagram DFA Ekivalen:

Jawaban dari Latihan Soal RE
1. (0+1)* 01
2. abb (a+b)*
3. (0+1)* 001 (0+1)*
4. (aa + ab + ba + bb)* b
5. ((01 (0+1)*) + ((0+1)* 01))
6. (0+1)* 1 (00+01+10+11)
7. ((a+b+c)* a (a+b+c)* b (a+b+c)*) +((a+b+c)* b (a+b+c)* a (a+b+c)*)

Read More

Teori Bahasa dan Automata - RE

RE (Regular Expression): Ekspresi sederhana untuk language yang diterima FA (Finite Automata)
Untuk setiap regular expression E, bahasa yang direpresentasikan dinotasikan dengan L(E)

 Basis:

- Konstanta Epsilon dan merupakan RE yang menunjukkan Empty Set

- Jika a adalah simbol dan a adalah RE. notasi ini menunjukkan language {a}, atau L(a)={a}.

- Variabel dengan huruf kapital merepresentasikan language

Induksi :

– Jika E dan F adalah RE, dan E + F adalah RE yang merepresentasikan union L(E) dan L(F). Atau L(E+F) = L(E) U L(F)

– Jika E dan F adalah RE, dan EF adalah RE yang merepresentasikan concatenation L(E) dan L(F). Atau L(EF) = L(E) L(F)

– Jika E adalah RE, dan E* adalah RE yang merepresentasikan closure dari L(E). Atau L(E*) = (L(E))*

Sifat-Sifat Regular Expression:

Contoh: (keterangan: ^+ = pangkat + atau positive closure)
- 00 = RE untuk {00}
- (0+1)* = RE untuk himpunan string yang terdiri dari 0 dan 1
- (0+1)*00(0+1)* = meliputi (epsilon)00(epsilon), 10010, 010011, ...
- (1+10)* = meliputi 1, 1010, 110, ...
- (0|1)*011 = meliputi 0011, 1011, 01011, ...
- (aa|ab|ba|bb)* = meliputi aa, aaab, aabb, ...
- (a|b)(a|b)(a|b)(a|b)* = meliputi aaaa, aaab, abbab, ...
- (aa|ab|ba|bb)^+ a = meliputi aaa, ababa, bbaaa, ...

LATIHAN!
Buat RE untuk:
1. Himpunan string dari alphabet {0, 1} yang diakhiri dengan 01
2. Himpunan string dari alphabet {a, b} yang diawali dengan abb
3. Himpunan string dari alphabet {0, 1} yang mengandung string 001
4. Himpunan string dari alphabet {a, b} yang diakhiri dengan b dan mempunyai panjang ganjil
5. Himpunan string dari alphabet {0, 1} yang diawali dan/atau diakhiri 01
6. Himpunan string dari alphabet {0, 1} yang simbol ketiga dari kanan merupakan angka 1
7. Himpunan string dari alphabet {a, b, c} yang mengandung sedikitnya satu buah a dan b

(Jawaban ada di akhir post Teori Bahasa dan Automata - Finite Automata)

Read More

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, ... }

Read More