Sifat Bahasa Reguler (Teori Bahasa dan Otomata)

Sifat Bahasa Reguler (Teori Bahasa dan Otomata)

1. Sifat Bahasa Reguler
Aji Purwinarko

2. PumpingLemma
•Pada tahun1961, Pumping Lemma yang merupakanmetode
untukmembuktikanregularitasdan iregularitassuatubahasa
ditemukanoleh Yehoshua Bar-Hillel, Micha A. P, dan
ElihauShamir.
•“Pumping“ adalahmenambahkanpanjangstring pada bagian
tengahword, tanpamengubahbagiandepandan belakangdari
suatustring.
•“Lemma“ dalamhaliniadalahTeoremakhususyang
membantudalammembuktikanbahwabahasayang diuji
adalahnonreguler.

3. •KonsepPemompaan=KonsepPerulangan
•Looppada gambardi atasdapatterjadiberulang-ulangataubisatidakterjadi
samasekali.
•Jika word !"#di ataskita“pumped”, makaword yang dihasilkanpada
bahasaautomata tersebutadalah!#, !"2#, !"3#, …

4. Untukword !, ", #di ataskitadapatmengasumsikankondisisebagaiberikut
(dimana$= jumlahstate pada automata):
1.|"| ≥ 1: setidaknyaadasatutransisiyang terjadipada loop
2.|!"| ≤ $: tidakadastateyang dilaluiduakali pada saattransisioleh word!"
kecualipada state %.

6. •Teori1
•MisalkanLadalahbahasaatassimbolΣ. JikaLditerimaoleh
suatuFAM=(Q,Σ,q0,A,δ)dan jikanadalahbanyaknyastate
dariM, makauntuksemuax ∈Lyang
memenuhi|x|≥nterdapatstringu, v, wsedemikian
hinggax=uvwdan ketigakondisidibawahiniterpenuhi:
1.!uv!!n
2.!v!>0
3.Untuksetiapi"0stringuviw# L

7. •Bukti
•Jika Ladalah bahasa reguler, maka terdapat FAyang secara pasti menerima
String-stringdi L. Seperti halnya FA –FA yang lainnya, mesin tersebut
hanya mempunyai state-stateyang terbatas, tetapi Lmempunyai string-
stringyang tak hingga. Hal ini berarti terdapat panjang string-stringyang
berbeda dalam L. Misalkan terdapat xyang merupakan beberapa untai
pada Lyang mempunyai panjang stringlebih dari jumlah stateyang ada
pada mesin. Ketika untai-untai tersebut menghasilkan suatu pathdalam
mesin, pathtersebut tidak bisa beranjak ke stateyang baru untuk setiap
abjad dalam stringkarena terdapat jumlah abjad (mengindikasikan panjang string) yang lebih banyak daripada jumlah statepada mesin.

8. •Maka pastilah terjadi balikan ke stateyang sama/terjadi siklus. Misal
xdipisahkan menjadi tiga bagian:
•Bagian1:Seluruhabjad-abjadpadaxsebelumsiklus
terjadi,ubisamerupakannullstring.
•Bagian2:vadalahbagiandalamsiklusitu.Karenapasti
terdapatsirkuit,vtidakdiperbolehkannullstring
•Bagian 3 : wadalah bagian setelah siklus . wbisa
dimungkinkan terbangun dari nullstring
Sehinggax=uvw
Untukx = uvnw, juga merupakan untai yang diterima padaL

9. ContohPumping Lemma RL
Diketahui
•L= {0n1 | n > 0}
BuktikanbahwaL merupakanRL!
Penyelesaian:
a.Ambil salah satustring dalamL, misal001 (acak, misaln=1)
b.Bentuklahsuatuformat uvwdaristring poina, yakniu=0,
v=0, dan w=1
c.UjikanketigasyaratPumping Lemma RL

10. •u=0, v=0, w=1, dan n=3
1.v≠empty 0≠empty → terpenuhi
2.|uv| ≤n |00|≤3 → terpenuhi
3.Untuksemuak> 0, string uvkwjuga merupakanstring dari
language L 0 0001→ terpenuhi
•Jika k bernilai0 makaterbentukstring 01 # L1
•Jika k bernilai1 makaterbentukstring 001 # L1
•Jika k bernilai2 makaterbentukstring 0001 # L1
L= {0n1 | n > 0} adalahRL

11. Sifat TertutupBahasa Regular
1.Gabungandariduabahasaregular adalahregular
2.Irisandariduabahasaregular adalahregular
3.Komplemendarisebuahbahasaregular adalahregular
4.Difference/bedadariduabahasaregular adalahregular
5.Reversal darisebuahbahasaregular adalahregular
6.Closure (star) darisebuahbahasaregular adalahregular
7.Perangkaiandaribahasa-bahasaregular adalahregular
8.Sebuahhomomorphism (substitusidaristring untuksimbol) darisebuahbahasaregular adalahregular.
9.Inverse homomorphism darisebuahbahasaregular adalahregular

12. Latihan
Buktikan bahwabahasaberikutapakahtermasukRL ataunon
RL
1.L1 = {01∪10}*
2.L2 = {0n10n| n ≥1}
3.L3 = {0n12n| n ≥1}
4.L4 = {anbn|n ≥ 0}