teori bahasa & otomata (bahasa & tatabahasa formal)
DESCRIPTION
TEORI BAHASA & OTOMATA (BAHASA & TATABAHASA FORMAL). PERTEMUAN II Y A N I S U G I Y A N I. MATERI PERTEMUAN II. BAHASA DAN TATA BAHASA FORMAL - TATA BAHASA (GRAMMAR) - KLASIFIKASI GRAMMAR - LATIHAN. TATA BAHASA (GRAMMAR). - PowerPoint PPT PresentationTRANSCRIPT
TEORI BAHASA & OTOMATA(BAHASA & TATABAHASA FORMAL)
PERTEMUAN IIY A N I S U G I Y A N I
MATERI PERTEMUAN IIBAHASA DAN TATA BAHASA
FORMAL- TATA BAHASA (GRAMMAR)- KLASIFIKASI GRAMMAR- LATIHAN
TATA BAHASA (GRAMMAR)
GRAMMAR ADALAH SUATU SISTEM MATEMATIK UNTUK
MENDEFINISIKAN BAHASA DAN ALAT UNTUK MEMBENTUK SUATU
STRUKTUR PADA KALIMAT BAHASA YANG DISEBUT SEBAGAI STRUKTUR GRAMATIK ATAU SINTAKS KALIMAT
TATA BAHASA (GRAMMAR)Spesifikasi dari bahasa
pemrograman meliputi : 1. Himpunan Simbol
2. Himpunan dari semua program yang secara sintaks benar3. Arti dari semua program yang secara sintaks benar
TATA BAHASA (GRAMMAR)Grammar terdiri dari himpunan
hingga yang tak hampa dari aturan atau produksi, yang menspesifikasikan sintaks dari bahasa.
Studi tentang grammar disebut teori bahasa formal
Ditekuni oleh Noam Chomsky pada tahun 1950
TATA BAHASA (GRAMMAR)Noam Chomsky membentuk
suatu model matematika untuk grammar, yang bersangkutan dengan studinya dalam bahasa natural.
Tahun 1960 konsep grammar digunakan dalam sintaks bahasa pemrograman ALGOL 60 yang menggunakan konsep grammar formal ini.
KONSEP MESIN ABSTRAKMetode lain untuk spesifikasi
bahasa adalah menggunakan konsep mesin abstrak, yang disebut akseptor (acceptor) atau penerima.
Akseptor ini akan menentukan apakah suatu untai (kalimat atau kata) termasuk bahasa.
TATA BAHASA (GRAMMAR)S = SentencesV = VerbO = ObjectA = ArticleSp = Subject PhraseN = NounVp = Verb PhraseNp = Noun Phrase
TATA BAHASA (GRAMMAR)S Sp VpSp ANA a | theN monkey | banana | cat |
mouse | treeVp VOV ate | climbsO NpNp AN
KLASIFIKASI GRAMMAR(DEFINISI 1.1)Sebuah Grammar didefinisi
sebagai 4 tupel G = (Vn, Vt, S, Q)
Vn = Simbol non terminalVt = Simbol terminalS = Simbol StartQ = Subhimpunan hingga yang
tidak kosong merupakan relasi (Vt U Vn) ke (Vt U Vn)
KLASIFIKASI GRAMMAR(DEFINISI 1.1)Secara umum sebuah elemen (, ) dari Q ditulis sebagai :
Dan disebut produksi atau rewriting
CONTOH DEFINISI 1.1
G1 = { Vn, Vt, S, Q }Dengan :Vn = { I, L, D }Vt = { a, b, ……, z, 0, 1, 2,……. ,
9 }S = IQ = { I L, I IL, I ID, L a, L
b, …., L z, D 0, D 1, ……., D 9 }
KLASIFIKASI GRAMMAR(DEFINISI 1.2)Untai w disebut penurunan atau
derivasi langsung dari v, ditulis sebagai v w
Untai vocabulary Q1 dan Q2 (termasuk untai hampa) anggota (Vn U Vt), sedemikian sehingga
V = Q1 Q2W = Q1 Q2 adalah produksi dari grammar G
CONTOH DEFINISI 1.2PRODUKSI Q1 Q2
I L I L
LL LX L X
LDL LIL D 1
LDDL L2DL D 2
KLASIFIKASI GRAMMAR(DEFINISI 1.3)G = (Vn, Vt, S, Q) adalah grammar.Untai v menghasilkan wW tereduksi dari v atau w adalah
diturunkan dari vDitulis sebagai v ==* w jika ada untai
vocabulary QoQ1,…, Qn (n>0) anggota (Vn U Vt)
sehingga :V = Q0 Q1
Q1 Q2Q n-1 Q n = w
CONTOH DEFINISI 1.3DARI DEFINISI 1.1
PERIKSA UNTAI a13
KLASIFIKASI GRAMMAR(DEFINISI 1.4)Bentuk sentensial adalah untai
yang dihasilkan melalui derivasi yang berawal dari simbol non terminal S
Bahasa L yang dibentuk oleh grammar G adalah himpunan semua bentuk sentensial yang semua simbolnya adalah simbol terminal.
Dengan kata lain :L(G) = { w | s ==* w, w anggota Vt*}
KLASIFIKASI GRAMMAR(DEFINISI 1.5) dan dalam produksi ,
disajikan sebagai = Q1 A Q2 dan = Q1 Q2
Jadi bentuk grammarnya berbentuk
Q1 A Q2 Q1 Q2
CONTOH DEFINISI 1.4, 1.5L (G2) = { an bn cn | n >= 1 }G2 = ( {S,B,C} , {a,b,c} , S , Q ) produksi Q =
S aSBC BC bcS abC CB BCbB bb cC cc
Periksa untai aabbcc