Ekspresi Reguler untuk Prefiks dan Sufiks aa

Di PR kuliah Teori Bahasa dan Automata, saya membuat satu soal di mana mahasiswa diminta membuat regex untuk himpunan semua string yang memiliki prefiks aa dan sufiks aa.

Setelah melihat sekilas lembar jawaban sekitar 126 orang mahasiswa, saya melihat bahwa sepertinya mayoritas menjawab regexnya  adalah aa(a \cup b)^*aa, yang secara telanjang memang sangat meyakinkan bahwa string-string yang dihasilkan oleh regex ini pasti memiliki prefiks aa dan sufiks aa.

Namun, sayangnya, regex ini salah karena tidak mencakup semua  string dengan prefiks dan sufiks aa. Panjang karakter string itu minimal adalah 4. Masih ada dua string yang belum termasuk, yaitu aa dan aaa.

Jadi, regex yang diharapkan adalah

aa \cup aaa \cup aa(a \cup b)^*aa.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s