Selasa, 07 Februari 2012
0 komentar

Teori Bahasa Automata



Definisi = Bahasa yang abstrak
Bahasa = Himpunan kata(Alfabet),Tata Bahasa
 = (a)
L = {a,aa,aaa,aaaa,aaaaa,...}
Dimana :
L = Language
 = Alfabet

Palindrome (Bahasa Baru) / Over Alfabet

 = {a,b}
Himpunan kata dari a dan b termasuk juga ‘null string’ = {e,a,b,ab,ba,...}
* = {ε,a,b,ab,ba,...}
Regular Expression / Operasi String
a.Language = {ε,x,xx,xxx,xxxx,...}, operasi stringnya L{x*}
b.Language = {ε,a,b,ab,ba,...}, operasi stringnya L{a+b}*

Finite Automata

Difinisi mesin FA
a.Himpunan State
b. = Input alfabet
c.ʆ = Fungsi transisi
d.start / finish state

Contoh simbol
Start State = 
Final State = 

Contoh soal
DFA
Definisi :
M = {Q, ʆ,s,f }
a = q0,q1,q2,q3
 = {a,b}
ʆ = Q x  = Q
s = { q0}
f = {q2}

Tabel Transisi

L(M) = {b,aba,aab,bbb,abbba,abaaa,aabbb,abbbaaa,aaabbbaaa,aabaaa,...}
Untuk aaaab
ʆ(q0,a) = q1
ʆ(q1,a) = q0
ʆ(q0,a) = q1
ʆ(q1,a) = q0
ʆ(q0,b) = q2(final state)
 
Toggle Footer
Top