15013-9-484675803350
TRANSCRIPT
-
7/25/2019 15013-9-484675803350
1/12
1
ATURAN PRODUKSISUATU FINITE STATE AUTOMATA
Aturan Produksi Bahasa Regular
Sebuah otomata berhingga menspesifikasikan sebuah bahasa sebagai himpunansemua untai yang menggerakkannya dari state awal ke salah satu dari stateyang diterimanya
(himpunan stateakhir). Otomata berhingga pada gambar 1 menerima ekspresi regular:
a(a* b*)b
Selain dengan ekspresi regular, kita dapat mengkonstruksi aturan-aturan produksi untuk
suatu tata bahasa regular. ita ingat !uga batasan aturan produksi untuk bahasa regular:
adalah sebuah symbol "ariabel
maksimal memiliki sebuah symbol "ariabel yang terletak di paling kanan bila ada.
(bisa diba#a : menghasilkan ), dimana atau bisa berupa symbol terminal atau symbol non-
terminal$"ariabel. Simbol "ariabel$non-terminal adalah symbol yang masih bisa diturunkan,
sedang symbol terminal sudah tidak bisa diturunkan lagi. Simbol terminal biasanya dinyatakan
dengan huruf ke#il, missal a,b,#. Simbol non-terminal$"ariabel biasanya dinyatakan dengan
huruf besar, missal %,&,'. Suatu tata bahasa (grammar) didefinisikan dengan tupel
({+,,,S}), dimana:
+ himpunan symbol "ariabel$non terminal
himpunan symbol terminal
kumpulan aturan produksi
S symbol awal
Selan!utnya akan kita lihat bagaimana membuat kumpulan aturan produksi untuk suatu
finite state automata.
PUSAT PENGEMBANGAN BAHAN AJAR UMB Puji Catur SiswipraptiniS.Kom
Teori Bahasa Otomata
-
7/25/2019 15013-9-484675803350
2/12
/
ambar 1. 0esin S%
Mengkonstruksi Aturan Produksi dari Suatu Finite State Automata
Dalam mengkonstruksi aturan produksi tata a!asa regular dari suatu finite state automata" perlu
kita ingat #ang men$adi per!atian kita adala! state-state#ang isa menu$u kestateak!ir% Mesinfinite
state automatadi gamar & memiliki input'a( dan '(% Simol 'a( dan '(akan men$adi s#mol terminal
pada aturan produksi #ang akan kita entuk% Misaln#a kita tentukan s#mol a)al adala! S% *ita
identikkan S dengan state a)al +,% Dari +,mendapat input a men$adi +&% Bisa kita tuliskan seagai aturan
produksi-
S
aEdimana E kita identikkan dengan +&.seenarn#a lei! tepatn#a adala! agian #ang elum terangkitkan
mulai dari state +&/% *ita isa menama!kan s#mol 0ariael aru setiap kali kita perlukan% Dari + &
mendapat transisi .tanpa menerima input/ ke +1dan +2% *ita tuliskan-
EA
EB
ila kita identikkan +1seagai A" dan +2seagai B% Dari +1 mendapat input a tetap ke +1" dan dari +2
mendapat input tetap ke +2" isa kita tuliskan-
AaA
BB
Selan$utn#a kita li!at dari +1mendapat input ke +3" dan dari +2mendapat input ke +3" sementara +3
stateak!ir dan dari +3tidak ada lagi usur keluar" maka isa kita tuliskan-
A
PUSAT PENGEMBANGAN BAHAN AJAR UMB Puji Catur SiswipraptiniS.Kom
Teori Bahasa Otomata
+1
+2
+3
+,
+&
a
a
-
7/25/2019 15013-9-484675803350
3/12
2
B
*umpulan aturan produksi #ang kita perole! isa kita tuliskan seagai erikut-
SaE
EA |B
AaA |B
BB |
4ngat '|( erarti atau% Se5ara 6ormal tata a!asa #ang diperole! dari otomata pada gamar &-
78 {S"E"A"B}
T 8 {a"}
P 8 {SaE" EA |B" AaA |B" BB | }
S 8 S
*ita li!at 5onto! lain pada gamar 1
Gambar 2% Mesin 9SA
*ita isa mengkonstruksi aturan produksi untuk otomata terseut-
T 8 {a"}
S 8 S
*umpulan aturan produksin#a kita uat seagai erikut-
SaA |B
PUSAT PENGEMBANGAN BAHAN AJAR UMB Puji Catur SiswipraptiniS.Kom
Teori Bahasa Otomata
+&
+:
+,
+3
+1
+2
+;
a
a
a
-
7/25/2019 15013-9-484675803350
4/12
.identikkan S untuk +," A untuk +&" B untuk +3/
A=? bila menerima untai yang memiliki akhiran /
simbol berturutan yang sama, atau se#ara formal dalam ekspresi regular:
(5@1)*(55@11)
'ontoh input yang diterima :
51511, 51155, 1515155, 15115155, 55, 11, 155, 511, 555, 111
onfigurasi dari 0esin 0ealy tersebut:
{45,41,4/}
{5,1}
{=,}
S 45
(45,5)
(45,1)
(41,5) =
(41,1)
(4/,5)
(4/,1) =
ambar /. 0esin 0ealy
PUSAT PENGEMBANGAN BAHAN AJAR UMB Puji Catur SiswipraptiniS.Kom
Teori Bahasa Otomata
+1
+,
+&
,>T
,>T
,>?
&>T
&>T
&>?
-
7/25/2019 15013-9-484675803350
10/12
15
Eki%alensi Mesin Moore dan Mesin Meal$
7ari suatu 0esin 0oore dapat dibuat 0esin 0ealy yang eki"alen, begitu !uga
sebaliknya. Antuk mesin 0ealy pada gambar / dapat kita buat 0esin 0oore yang eki"alen yaitu
gambar 2. &isa kita lihat statepada mesin 0oore dibentuk dari kombinasi statepada 0ealy dan
banyaknya output. arena !umlah state 0ealy 2, dan !umlah output /, maka !umlah state
pada 0oore yang eki"alen 8.
&isa dilihat konfigurasi 0esin 0oore yang dibentuk:
{45=, 45, 41=,41, 4/=,4/}
{5,1}
{=,}
S 45
(45=) =
(45)
(41=) =
(41)
(4/=) =
(4/)
PUSAT PENGEMBANGAN BAHAN AJAR UMB Puji Catur SiswipraptiniS.Kom
Teori Bahasa Otomata
-
7/25/2019 15013-9-484675803350
11/12
11
ambar 2. Mesin Moore yang ei!alen dengan gambar "
&ila kita perhatikan dari gambar diatas, state45= dapat dihapus karena tidak ada busur
yang mengarah ke statetersebut.
Antuk memperoleh eki"alensi mesin 0ealy dari suatu mesin 0oore #aranya lebih mudah, #ukup
dengan menambahkan label outputke setiap transisi dan menghapus label outputpada setiap
state. ita lihat gambar merupakan mesin 0ealy yang eki"alen dengan mesin 0oore pada
gambar 1.
onfigurasi 0esin 0ealy tersebut:
{45, 41, 4/}
{5,1}
{5,1,/}
S 45
(45,5) 5
(45,1) 1
(41,5) /
(41,1) 5
(4/,5) 1
(4/,1) /
PUSAT PENGEMBANGAN BAHAN AJAR UMB Puji Catur SiswipraptiniS.Kom
Teori Bahasa Otomata
+1T
+,T
+&T
+1
?
+,
?
+&
?
, ,
&
&
&&
&
,&
T
,,
T
, T
,
?
,?
,
?
,
,
,
T
,
-
7/25/2019 15013-9-484675803350
12/12
1/
!am"ar &. Mesin Mealy yang ei!alen dengan gambar1.
PUSAT PENGEMBANGAN BAHAN AJAR UMB Puji Catur SiswipraptiniS.Kom
Teori Bahasa Otomata
+1
+,
+&
&>, ,>&
,>,
&>& ,>1
&>1