Teori Bahasa dan Automata 2021

Anda sedang membaca : Teori Bahasa dan Automata

Ekspresi Reguler

Ekspresi reguler merupakan suatu cara yang digunakan untuk menspesifikasikan bahasa dengan memberikan suatu pola / pattern untuk untai / string dari suatu bahasa. Ekspresi reguler merupakan bahasa reguler yang dapat diterima Finite State Automata (FSA). Sebuah bahasa dapat disebut sebagai bahasa reguler jika terdapat FSA yang menerimanya atau dari state awal berakhir di state akhir.

Ada 4 notasi ekspresi reguler :

1. Closure (*), pada notasi asterik string dapat muncul sebanyak 0,…n kali. Contoh a* = {ε, a, aa, aaa,…, dst}
2. Closure (⁺), pada notasi ini string dapat muncul sebanyak 1,…n kali. Contoh a⁺ = {a, aa, aaa,…, dst}
3. Alternation (+), pada notasi ini dapat dilambangkan dengan tanda +, U(gabungan), dan #. Paada notasi ini sesuai dengan namanya alternation artinya kita dapat memilih salah satu, contoh 1+2 = {1, 2} atau {2, 1}
4. Concatenation (.), pada notasi ini simbol akan digabung menjdadi string dan tidak berlaku hukum komutatif contohnya a.b maka menjadi ab dan 1.2 akan menjadi 12 (satu dua, bukan dua belas).

Baca juga :

• Cara Mendapatkan Canva Pro Gratis Melalui Github Education Dengan Email Mahasiswa 2021
• Cara Mendapatkan Update Windows 11
• Cara Kecilkan Ukuran Video Dengan Handbrake Gratis 2021
• 3 Plugin Chrome Yang Wajib Dimiliki Web Designer!
• Cara Membuat Linktree Sendiri Dengan HTML dan CSS 2021

Grammar (Tata Bahasa)

Pengertian

Bahasa merupakan himpunan kalimat baik tertinggi maupun tak terhingga. Pada tata bahasa atau grammar alfabet disebut sebagai simbol terminal atau token, sedangkan kalimat merupakan deretan hingga simbol -simbol terminal.

Definisi

Sebuah tata bahasa didefinisikan sebagai 4 tupel yaitu G = (V, T, S, P/Q) dimana :

• V (Simbol non terminal)
  Simbol non terminal merupakan simbol yang dapat diturunkan kembali menjadi simbol terminal atau simbol non terminal lainnya. Yang termasuk kedalam simbol terminal yaitu :
  – Huruf besar (A, B, C,…)
  – Huruf S sebagai simbol awal (start)
  -String yang tercetak miring seperti expr.
• T (Simbol Terminal)
  Kebalikan dari simbol non terminal, simbol terminal merupakan simbol yang tidak dapat diturunkan lagi. Yang termasuk kedalam simbol terminal yaitu :
  – Huruf kecil (a, b, c, …)
  – Simbol operator (+, -)
  – Simbol tanda baca (‘(‘, ‘)’, ‘,’, ‘;’).
  – String yang tercetak tebal (if, then, else).
• S (Elemen anggota V yang disebut simbol start)
• P/Q (Aturan Produksi)
  Aturan produksi dapat dinyatakan dalam bentuk α → β dimana :
  – α Menyatakan simbol -simbol pada ruas kiri aturan produksi (minimal 1 non terminal)
  – β Menyatakan simbol – simbol pada ruas kanan aturan produksi.
  Simbol tersebut dapat berupa simbol terminal maupun non terminal.

Konversi Grammar ke Ekspresi Reguler

Contoh Soal 1

G1 : T = {a}, V = {S}, Q = {S → aS | a}
aaS | aa | a
aaaS | aaa | aa | a
L = {a, aa, aaa,…,}
ER = a⁺
Pada soal G1 terdapat simbol terminal (T) yaitu a dan simbol terminal (V) yaitu S, dan aturan produksinya (Q) adalah {S → aS | a} cara membacanya : S menjadi a kecil S besar atau a kecil.

Referensi

1. Tan, R. (n.d.). Grammar Dan Bahasa automata – ppt download. SlidePlayer. Retrieved October 13, 2021, from https://slideplayer.info/slide/15751727/.