3. Bahasa Reguler dan Tata Bahasa reguler

Teori Bahasa dan Otomata

1. Bahasa Reguler dan Tata
Bahasa Reguler
Aji Purwinarko

2. Bahasa Reguler
•Kita telah mendefinisikan bahasa reguler, mempelajari beberapa cara di mana bahasa reguler dapat diwakili dan telah melihat beberapa contoh
kegunaannya.
•Pertanyaan pertama yang kita ajukan adalah apa yang terjadi ketika kita
melakukan operasi pada bahasa reguler?
•Operasi yang kita gunakan adalah operasi himpunan sederhana, seperti
penggabungan, serta operasi di mana setiap stringbahasa diubah.
•Apakah bahasa yang dihasilkan masih teratur? Kita menyebutnya
sebagai closure. Sifat-sifat closuresebagian besar digunakan untuk kepentingan
teoretis, membantu kita dalam membedakan berbagai rumpun bahasa yang
akan kita jumpai.

3. •Serangkaianpertanyaan kedua tentang rumpun bahasa berhubungan dengan kemampuan kita untuk memutuskan sifat-sifat tertentu. Misalnya, dapatkah kita mengetahui apakah suatu bahasa terbatas atau tidak? Seperti yang akan kita lihat, pertanyaan-pertanyaan seperti itu mudahdijawab untuk bahasa-bahasa biasa, tetapi tidak semudah itu untuk rumpun bahasa lain.
•Bagaimana kita dapat mengetahui apakah suatu bahasa tertentu teratur atau tidak?Jika bahasa tersebut sebenarnya reguler, kita selalu dapat menunjukkannya dengan memberikan beberapa DFA, ekspresi reguler, atautata bahasa reguler. Tapi jika tidak, kita perlu cara lain. Salah satu cara untuk menunjukkan suatu bahasa tidak teratur adalahdengan mempelajari sifat-sifat umum bahasa reguler, yaitukarakteristik yang dimiliki oleh semua bahasa reguler. Jika kita mengetahui beberapa sifat seperti itu, dan jika kita dapat menunjukkan bahwa bahasa kandidat tidak memilikinya, maka kita dapat mengatakan bahwa bahasa tersebut tidak teratur.

4. PenggabunganAutomata
•Penggabungandapatdilakukandng2 Cara
•Paralel
•Serial
•Untukpenggabunganparallel automata M dan N, darisymbol automata
yang baru, kitabentukkemungkinan2 transisiuntuksymbol awaldari
string. Transisipertamadariawalstate barukestate yang adapada state(M)
yang dapatdicapaidengansymbol tersebutsebagaiinput pertamapada M.
kemungkinantransisikeduauntuksymbol yang samasehinggamencapai
state pada state(N) jikatersebutadalahinputyang pertamapada N. daristete
iniautomata baruberaksisebagaiM atauN. Penyesuaianlain yang perlu
dilakukanadalahmembuatstate awalmenjadiaccepting jikaautomata menerimastring kosong. Automata iniakanmenerimaBahasa gabungan
dariBahasa yang diterimaoleh M dan N.

5. •Proses penggabungandariautomata A dan A’ dengancaraparallel untuk
membentuknon-deterministic automata M
1.Kita asumsikanbahwastate(A) dan state(A’) adalahdisjoint dan tak
satupundisebutstate awalS0
2.#$%$&'={S0}∪#$%$&)∪#$%$&()′)
3.#$%$&%.%/'=S0
4.Jika 01#$%$&()), makafungsitransisi$2%34545'(s,x)
=fungsi$2%34545)(4,0)
5.Jika 01#$%$&()′), makafungsitransisi$2%34545'(s,x)
=fungsi$2%34545)′(4,0)
6.Fungsi$2%34545(')(4,00)= fungsitransisi$2%34545())(s,State
awal(A))∪fungsitransisi$2%34545()′)(s,Stateawal(A’))
7.)FF&G$53H'=)FF&G$53H)∪)FF&G$53H)!, jikatidakada
salah satumesinyang menerimastring kosong, dan)FF&G$53H'=
)FF&G$53H)∪)FF&G$53H)!∪{#0}, jikaadasalah satumesin
yang menerimastring kosong

8. •Menggabungkan automata secaraserial adalahsuatuide untukmembentuknondeterministic automata yang menghasilkanstring yang terdiridaristring pada suatuBahasa diikutidenganstring pada Bahasa yang lain
•Proses penggabungandariautomata A dan A’ dengancaraserial untukmembentuknon-deterministic automata M
1.Kita asumsikanbahwastate(A) dan state(A’) adalahdisjoint dan taksatupundisebutstate awalS02.#$%$&'={S0}∪#$%$&)∪#$%$&()′)
3.#$%$&%.%/'=#$%$&)
4.Jika 01#$%$&()′), makafungsi$2%34545)′(s,x)=fungsi$2%34545)′(4,0)
5.Jika 01#$%$&()), dan 0bukanaccepting state,makafungsi$2%34545'(s,x)=fungsi$2%34545)(4,0)
6.Jika 01#$%$&()), dan 0accepting state, makafungsi$2%34545(')(4,0)= fungsitransisi$2%34545())(s,Stateawal(A))∪fungsitransisi$2%34545()′)(Stateawal(A’),x)
7.)GG&H$53I'=)GG&H$53I)∪)GG&H$53I)!, jikaA’ menerimastring kosong, dan )GG&H$53I'=)GG&H$53I()!), jikaA’ tidakmenerimastring kosong

10. EkspresiRegular
•EkspresiRegular(Regular Expression) adalahsuatucarakompak(compact way) untukmerepresentasikanataumenggambarkanBahasa
regular
•Notasiinimelibatkankombinasistring simboldaribeberapaalfabetyang
disimbolkanΣ, tandakurung, dan operator +, ., dan *. Kasuspaling
sederhanaadalahbahasa{#}, yang akandilambangkandenganekspresi
reguler#. Contohlain adalahbahasa{#,&,'}, di mana, menggunakan+
untukmenunjukkanunion(gabungan), kitamemilikiekspresireguler#+
&+'. Kita menggunakan·untukpenggabungan“dan”, dengancarayang
sama*untukstar-closureyang menunjukkanperulangan. Ekspresi(#+(&·'))∗adalahsingkatandaristar-closuredari{#}⋃; {&}, yaitubahasa
{.,#,&',##,#&',&'#,&'&',###,##&',...}.

11. DefinisiFormal dariEkspresiReguler
Ekspresiregulardibangundarikonstituenprimitifsecaraberulangkalidenganmenerapkanaturanrekursiftertentu.Halinimiripdengancara
membangunekspresiaritmatik.
Definisi4.1
DiberikanΣsebagaialfabet. Kemudian
1.1,.dan #∈Σsemuanyaadalahekspresireguler. Inidisebutekspresi
regulerprimitif.
2.Jika 3"dan 3#adalahekspresireguler, demikianjuga 3"+3#, 3".3#,3"∗, dan
(3").
3.Sebuahstring adalahekspresiregulerjikadan hanyajikadapatditurunkan
dariekspresiregulerprimitifdengansejumlahangkaterbatasyang
menerapkanaturan(2).

12. Bahasa TerkaitdenganEkspresi
Reguler
Ekspresiregulerdapatdigunakanuntukmenggambarkanbeberapabahasasederhana.Jika!adalahekspresireguler,kitaakanberikan"(!)yangmenunjukkanbahasayangterkaitdengan!.
Definisi4.2
Bahasa "(!)dilambangkandenganekspresiregulerapapun dari!didefinisikanoleh aturanberikut.
1.'adalahekspresireguleryang menunjukkanhimpunankosong,
2.)adalahekspresireguleryang menunjukkan{)}.
3.Untuksetiap,∈Σ, ,adalahekspresireguleryang menyatakan{,}. Jika !"dan !#adalahekspresireguler, maka
4."(!"+!#)="(!")∪"(!#),
5."(!"⋅!#)="(!")∪"(!#);
6."((!"))="(!"),
7."(!"∗)=("(!"))∗.

13. Sifat-sifatEkspresiRegular
•Ekspresi regular mempunyaibeberapasifat-sifatyang dapatdigunakanuntukmengurangikompleksitasdariekspresiregular atauuntukmembuktikanbahwaduaekspresiregular merepresentasikanBahasa yang sama
•MisalA, B, C adalahekspresiregular, maka
1.)+N=N+)(Sifat communicative darialternation)
2.∅∗=P(closure darihimpunankosong)
3.)+(N+Q)=()+N)+Q(Sifat associative darialternation)
4.)(NQ)=()N)Q(Sifat associative dariconcatination)
5.)(N+Q)=)N+)Q(Sifat distributive concatinationatasalternation)
6.)P=P)=)(Sifat identity darihimpunanconcatination)
7.∅E=E∅=∅(Sifat zero concatination)
8.E∗=E+E∗
9.(E∗)∗=E∗
10.E+∅=E(Sifat identity darihimpunanalternation)

14. Latihan
TuliskanRegex untukBahasa berikut
1.{bc, abc} = (∅+a)bc
2.(λ, ab, abab, abab, ...)= (ab)*
3.(λ, a, b, aa, ab, ba, bb, aaa, ...) = (a+b)*
4.(a,λ, b, bb, bbb, ...)= a+b*
5.(λ, a, aa, aaa, aaaa, ...)= (a+∅)*
UbahRE berikutmenjadiNFA
1.a+∅*
2.(a+∅)*