Teori Bahasa Otomata : Dasar-Dasar TBO

Berikut ini merupakan beberapa terminologi dasar dari teori bahasa, yaitu :

1. Simbol
2. Alphabet 
3.  String

Dalam teori bahasa : 

Istilah huruf = karakter = simbol

Istilah kalimat = kata = string

• Simbol/huruf/karakter yaitu sebuah elemen karakter yang memiliki makna unik. Ex: symbol A
• Alphabet merupakan himpunan tak koson yang berhingga dari simbol-simbol.
• Kata/kalimat/string yaitu deretan simbol-simbol dari alphabet. Ex: C={a,b,c,1,2,3}

Disini saya akan memberikan soal kuliah saya beserta jawaban tentang dasar-dasar TBO:

(1.) Jika a, b, c dan d adalah simbol, maka dapat dibangun beberapa string  dari keempat simbol tersebut : 

• String w = abcda 
• String y = abbcdbc 
• String z = abcdbbac

a. Tentukan panjang string w, y, dan z? |w|=5 , |y|=7, |z|=8.  

b.  Tentukan Prefik dari string w,y, dan z adalah

                w = abcda, abcd, abc, ab, a dan ε semua adalah Prefix(w).

                y = abbcdbc, abbcdb, abbcd, abbc, abb, ab, a, dan ε semua adalah Prefix(y).

                z = abcdbbac, abcdbba, abcdbb, abcdb, abcd, abc, ab, a dan ε semua adalah Prefix(z).

c. Tentukan Postfix dari string w,y, dan z adalah

                w = abcda, bcda, cda, da, a dan ε semua adalah Postfix(w).

                y = abbcdbc, bbcdbc, bcdbc, cdbc, dbc, bc, c dan ε semua adalah Postfix(y).

                z = abcdbbac, bcdbbac, cdbbac, dbbac, bbac, bac, ac, c dan ε semua adalah Postfix(z).

(2.) Diketahui string r = uad, dan h = 5678. Tentukan  Concatination dan string r dan h!

jawaban : Concate(rh) = rh = uad5678

(3.) Tentukan substring dan subsequense string dari "tidy" !

jawaban : Substring = tidy, tid, idy, ti, id, dy, t, i, d, y, dan ε.

    Subsequense = tidy, tid, idy, tiy, tdy, ti, td, iy, dy, t, i, d, y, dan ε.

(4.)  Misalkan A={the, my} dan B={horse, house, hose} merupakan bahasa-bahasa berdasarkan abjad Bahasa Inggris. Carilah A.B, A.A.B, dan B.B !

jawaban :   a. A.B = {thehorse, thehouse, thehose, myhorse, myhouse, myhose}.

b. A.A.B  à A.A = {thethe, themy, mythe, mymy}

A.A.B = {thethehorse, thethehouse, thethehose, themyhorse, themyhouse, themyhose, mythehorse, mythehouse, mythehose, mymyhorse, mymyhouse, mymyhose}.

c. B.B = {horsehorse, horsehouse, horsehose, househorse, househouse, househose, hosehorse, hosehouse, hosehose}.

(5.)  Tentukan apakah produksi-produksi berikut memenuhi aturan tata bahasa context sensitif : 

• BaC -> Ab 
• S -> aBCDF 
• Ab -> cde

Jawaban:

a. BaC à AB (tidak memenuhi aturan karena ruas sebelah kiri jumlah lebih besar dibandingkan ruas sebelah kanan. Seharusnya menurut aturan “Ruas sebelah kiri lebih kecil atau sama jumlahnya dengan ruas sebelah kanan”).

b. S à aBCDF (memenuhi aturan tata Bahasa context senstif).

c. Ab à cde (memenuhi aturan tata Bahasa context senstif)

Semoga Tugas yang saya kerjakan ini bisa bermanfaat bagi yang membutuhkan :)

Se