Selasa, 04 Oktober 2011

Teori Bahasa

•Teori bahasa membicarakan bahasa formal (formal language), terutama untuk kepentingan perancangan kompilator (compiler) dan pemroses naskah (text processor).
•Bahasa formal adalah kumpulan kalimat. Semua kalimat dalam sebuah bahasa dibangkitkan oleh sebuah tata bahasa (grammar) yang sama.
•Sebuah bahasa formal bisa dibangkitkan oleh dua atau lebih tata bahasa berbeda.
•Dikatakan bahasa formal karena grammar diciptakan mendahului pembangkitan setiap kalimatnya.
•Bahasa Natural/manusia bersifat sebaliknya; grammar diciptakan untuk meresmikan kata-kata yang hidup di masyarakat. Dalam pembicaraan selanjutnya ‘bahasa formal’ akan disebut ‘bahasa’ saja.

Otomata (Automata)
•Otomata adalah mesin abstrak yang dapat mengenali (recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu.

Beberapa Pengertian Dasar :
•Simbol adalah sebuah entitas abstrak (seperti halnya pengertian titik dalam geometri). Sebuah huruf atau sebuah angka adalah contoh simbol.
•String adalah deretan terbatas (finite) simbol-simbol. Sebagai contoh, jika a, b, dan c adalah tiga buah simbol maka abcb adalah sebuah string yang dibangun dari ketiga simbol tersebut.
= 4.w dan didefinisikan sebagai cacahan (banyaknya) simbol yang menyusun string tersebut. Sebagai contoh, jika w = abcb maka w•Jika w adalah sebuah string maka panjang string dinyatakan sebagai
= 0. String hampa dapat dipandang sebagai simbol hampa karena keduanya tersusun dari nol buah simbol. (atau ^) sehingga •String hampa adalah sebuah string dengan nol buah simbol. String hampa dinyatakan dengan simbol
•Alfabet adalah hinpunan hingga (finite set) simbol-simbol

Operasi Dasar String
Diberikan dua string : x = abc, dan y = 123
•Prefik string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling belakang dari string w tersebut.
 adalah semua Prefix(x)Contoh : abc, ab, a, dan
•ProperPrefix string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling belakang dari string w tersebut.
 adalah semua ProperPrefix(x)Contoh : ab, a, dan
•Postfix (atau Sufix) string w adalah string yang dihasilkan dari string w dengan menghilangkan nol atau lebih simbol-simbol paling depan dari string w tersebut.
 adalah semua Postfix(x)Contoh : abc, bc, c, dan
•ProperPostfix (atau PoperSufix) string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol paling depan dari string w tersebut.
 adalah semua ProperPostfix(x)Contoh : bc, c, dan
•Head string w adalah simbol paling depan dari string w.
Contoh : a adalah Head(x)
30 Juli 2009 15.59

Anonim mengatakan...
Nama : KHOIRUN NISA'
NIM  : 120911077

Bahasa dan otomata merupakan bahasa Formal yaitu suatu kalimat dibentuk dengan menerapkan serangkaian aturan produksi pada sebuah
simbol ‘akar’. Proses penerapan aturan produksi dapat digambarkan sebagai suatu
diagram pohon.

Operasi Dasar String
ProperPostfix (atau PoperSufix) string wadalah string yang dihasilkan dari string wdengan menghilangkan satu atau lebih simbol-simbol paling depan dari string wtersebut.

 adalah semua ProperPostfix(x)Contoh : bc, c, dan

a.Head string w adalah simbol paling depan dari string w.
Contoh :a adalah Head(x)

b.Tail string w adalah string yang dihasilkan dari string wdengan menghilangkan simbol paling depan dari string w tersebut.
Contoh : bc adalah Tail(x)

c.Substring string wadalah string yang dihasilkan dari string wdengan menghilangkan nol atau lebih simbol-simbol paling depan dan/atau simbol-simbol paling belakang dari string wtersebut.
 adalah semua Substring(x)Contoh : abc, ab, bc, a, b,c, dan

Berkaitan dengan teori mesin abstrak, yaitu mesin sekuensial yang menerima input, dan
mengeluarkan output, dalam bentuk diskrit.
Contoh :
♦ Mesin Jaja / vending machine
♦ Kunci kombinasi
♦ Parser/compiler
Teori Otomata dan bahasa formal, berkaitan dalam hal :
♦ Pembangkitan kalimat/generation : menghasilkan semua kalimat dalam bahasa L
berdasarkan aturan yang dimilikinya
♦ Pengenalan kalimat / recognition : menentukan suatu string (kalimat) termasuk
sebagai salah satu anggota himpunan L.
31 Juli 2009 14.06

Otomata

Arti menurut American Heritage Dictionary :
1. Robot.
2. One that behaves in an automatic or mechanical fashion.
Arti dalam Matematika.
Berkaitan dengan teori mesin abstrak, yaitu mesin sekuensial yang menerima input, dan mengeluarkan output, dalam bentuk diskrit.
contoh:
1. Mesin jaja/vending machine
2. Kunci kombinasi
3. parser/compiler

Bahasa formal.
suatu kalimat dibentuk dengan menerapkan serangkaian suatu aturan produksi pada sebuah simbul 'akar'. Proses penerapan aturan produksi dapat digambarkan suatu diagram pohon.

Sifat-sifat otomata:
1. kelakuan mesin bergantung pada rangkaian masukan yang diterima mesin tersebut.
2. setiap saat, mesin dapat berada pada suatu status tertentu dan dapat berpindah kestatus baru karena adanya perubahan input.
3. Rangkaian input (diskrit)pada mesin otomata dapat dianggap sebagai bahasa yang harus "dikenali" oleh sebuah otomata. setelah pembacaan input selesai, mesin automata kemudian membuat "keputusan".


Jenis-jenis automata.
jenis pita masukkan Arah head Memory
Finite State Read Only 1arah -
Push Down Read Only 1arah stack
Liner-Bounded R/W 2arah (bounded)
Turing-Machine R/W 2arah (unbuended)


didalam bahasa Otomata ada yang namanya kecerdasan buatan.
Kecerdasan Buatan.
kecerdasan buatan adalah bidang ilmu yang mendasarkan bagaimana sebuah komputer bisa bertindak seperti dan sebaik manusia.
Aplikasi Kecerdsan buatann:
1.Sistem pakar.
2.Pengolahan bahasa alami.
3.Pengenalan ucapan.
4.Robotika dan sistem sensor.
5.Computer Vision.
6.Problem solving and planning.
7.Permainan.

Otomata dan Bahasa Formal

1. Otomata hingga
Otomata hingga melibatkan stata dan transisi antar stata yang merupakan tanggapan atas masukan. Otomata hingga berguna untuk merekayasa perangkat lunak-perangkat lunak tertentu termasuk komponen lexical analyzer yang terdapat pada compiler dan sistem pemeriksa kebenaran pada sirkuit atau protocol.
Automata merupakan suatu studi abstrak yang terdiri dari suatu himpunan tiga tupel yaitu M={S, S, D} dimana S menyatakan state (keadaan); S menyatakan input; dan D menyatakan penentuan keadaan nilai.
Subjek utama dalam tulisan ini adalah mesin sekuensial, sebuah struktur penting yang menjadi dasar dari pirantipiranti, aktivitas, dan proses pengambilan keputusan, terutama yang berhubungan dengan komputer.
Automata merupakan suatu sub struktur utama dari mesin atau proses sekuensial tersebut. Pada mesin sekuensial, suatu proses dibangkitkan oleh masukan tertentu dan menghasilkan keluaran tertentu pula berdasarkan informasi yang dimiliki.
Automata merupakan struktur transisi dari suatu mesin sekuensial, dengan demikian pada dasarnya automata adalah bagian dari suatu mesin sekuensial dengan struktur keluaran yang telah dihapus.
Automata adalah mesin abstrak yang dapat mengenali (recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu Pemodelan geografis berbasiskan Cellular Automata (CA) dan Multi Agent System (MAS) memiliki kekurangan:

• Pada Cellular Automata, automata secara individual dapat menyebarkan informasi, tapi tidak bebas bergerak
• Pada Multi Agent System, automata bergerak secara bebas dan mandiri, tetapi mengabaikan sifat-sifat ruang (space) dan keruangan (spasial).
Cellular Automata
Automata merupakan bentuk jamak dari automaton. Automaton adalah suatu mekanisme pemrosesan secara diskrit, berdasarkan keadaan internal dari suatu obyek. Dalam automata, obyek (sel atau agent) memiliki keadaan dan aturan yang menentukan perubahan.
Berikut sifat-sifat dari Automaton:
• Berganti keadaan menurut waktu
• Sesuai seperangkat aturan
• Berdasarkan keadaan internal dan eksternal
• Dalam langkah yang berurutan.
1.2 .Ekspresi Reguler
Exspresi regular merupakan notasi structural untuk mendeskripsikan pola-pola yang sama dan dapat diwakili oleh otomata hingga. Exspresi regular digunakan pada berbagai tipe perangkat lunak yang biasa kita gunakan, termasuk perangkat lunak untuk mencari pola-pola dalam texs atau nama file.
1.3. Tata Bahasa Bebas-Konteks
Tata bahasa bebas konteks ini merupakan notasi penting yang digunakan untuk mendeskripsikan sruktur bahasa pemograman dan himpunan-himpunan untai yang berhubungan; digunakan untuk membuat komponen parser pada compiler.
1.4. Mesin Turing
Mesin turing adalah otomata yang menjadi model computer yang kita kenal saat ini. Mesin turing memungkinkan kita untuk mempelajari decidability, yaitu pertanyaan mengenai apa yang dapat dan tidak dapat dikerjakan oleh computer. mesin ini juga memungkinkan kita menbedakan tractable problem (dapat dipecahkan dalam waktu polynomial) dari intractable problem (tidak dapat dipecahkan dalam waktu polynomial).
1.5. Pembuktian Deduktif
Metode pembuktian yang mendasar ini dilakukan dengan cara mendaftar stateman yang diketahui benar atau yang secara logika mengikuti beberapa statemen sebelumnya.
1.6. Pembuktian stetemen jika-maka
Banyak teorema memiliki bentuk “jika (sesuatu) maka (sesuatu yang lain)”. Stateman tersebut atau stateman yang mengikuti “jika” merupakan hipotesis dan yang mengikuti “maka” adalah kesimpulan. Pembuktian deduktif statemen jika-maka dimulai dengan hipotesis dan dilanjutkan dengan statemen yang mengikuti secara logika hipotesis dan statemen sebelumnya, hingga kesimpulan dibuktikan sebagai salah satu statemen.
1.7. Pembuktian stateman jika dan hanya jika
Ada teorima-teorema yang memiliki bentuk “(sesuatu) jika dan hanya jika (sesuatu yang lain)”. Statemen-statemen tersebut dibuktikan dengan cara statemen “jika-maka” pada kedua arah. Jenis teorema yang sama mengklain kasamaan himpunan-himpunan yang dideskripsikan dengan dua cara yang berbeda;
1.8. Pembuktian Kontrapositif
Pembuktian kontrapositif kadang kala,  lebih mudah untuk membuktikan statemen “jika H maka C” dengan membuktikan “jika hal dan bukan C maka (sesuatu yang diketahui salah).” Pembuktian dengan cara ini disebut sebagai pembuktian dengan kontradiksi.
1.9. Counter example:
Tidak jarang kita diminta untuk menunjukan bahwa suatu statemen tertentu tidak benar. jika statemen memiliki satu atau lebih para meter, makakita dapat menunjukan bahwa statemen tersebut salah sebagai suatu generalisasi dengan menyediakan satu saja counterexample, yaitu suatu penetapan/penyerahan nilai kepada parameter yang membuat statemen tersebut salah.
1.10. Pembuktuan Induktif
Statemen yang memiliki parameter bilangan bulat n sering kali dapat dibuktikan dengan induksi pada n. kita membuktikan statemen tersebut benar atau basis, yaitu sejumblah berhingga kasus untuk nilai n tertentu dan kemudian membuktikan langkah induktif: bahwa jika statemen bernilai benar untuk nilai-nilai hingga n, maka ia juga bernilai benar untuk n + 1.
1.11. Intruksi Struktural
Pada beberapa situasi, teorema yang akan dibuktika secara induktif teorema mengenai suatu kontruksi yang didefinisikan secara rekursif , misalnya pohon (tree). Kita dapat membuktikan teorema mengenai obyek-obyek yang dikontruksi melalui induksi pada jumblah langkah yang digunakan untuk mengkontruksinya. Jenis intruksi ini dirujuk sebagai structural.
1.12. Alfabet
Alphabet adalah sembarang himpunan simbul-simbul.
1.13. Untai (string):
Untai adalah deretan simbul-simbul yang panjangnya berhingga.
1.14. Bahasa Dan Problema
Bahasa adalah himpunan (bisa jadi himpunan tak hingga) untai-untai, seluruhnya memilih timbulnya dari satu alphabet yang sama. Ketika suatu untai bahasa ditafsirkan denggan suatu cara pertanyaan mengenai apakah untai tersebut berada dibahasanya sering disebut sebagai problema.
Bahasa suatu Automata
Otomaton menerima untai-untai. Suatu untai diterima jika sejak dari stata mula, alihan yang disebabkan oleh pemrosesan sombol-simbol untai-untai tersebut. diagram alihan, untai diterima jika terdapat label lintasan dari stata mula kesuatu stata penerima.
• Kontruksi himpunan bagian
Dengan memperlakukan himpunan stata NFA sebagai stata suatu DFA, kita dapat mengkonfersi sembarang NFA menjadi DFA penerima bahasa yang sama.
Teori Bahasa Automata Dalam Ilmu Komputer
Suatu teori hanya menarik jika dapat membantu dalam mencari solusi terbaik. Tanpa penerapan timbul pertanyaan, mengapa mempelajari teori?
Teori memberikan konsep dan prinsip yang menolong untuk memahami perilaku dari suatu persoalan yang berkorelasi dengan teori tersebut. Bidang ilmu komputer meliputi topik yang luas, dari perancangan mesin sampai pemrograman. Disamping perbedaan yang ada, terdapat keseragaman prinsip-prinsip umum yang dipakai. Untuk mempelajari prinsip-prinsip dasar tersebut, kita mengkonstruksi suatu mesin otomata sebagai model abstrak dari komputer dan komputasi.

Teori bahasa membicarakan bahasa formal (formal language), yang terdiri dari kumpulan kalimat. Sebuah kalimat dalam sebuah bahasa dibangkitkan oleh sebuah tata bahasa (grammar) yang sama oleh dua atau lebih tata bahasa yang berbeda terutama untuk kepentingan perancangan kompilator (compiler) dan pemroses naskah (text processor).

Bahasa dalam hal ini berisi semua string yang dapat dihasilkan menggunakan aturan-aturan grammar yang mempunyai nilai/ manfaat sangat besar di ilmu informatika/ computer karena untuk mendeskripsikan dan mendefinisikan sintaks bahasa pemrograman dan bahasa-bahasa formal lain dan dapat diterapkan pada perancangan kompilator.

Teori otomata merupakan kajian mengenai perangkat komputasi abstrak atau bisa dikatakan mesin abstrak. Teori menyediakan konsep-konsep dan prinsip-prinsip yang dapat membantu kita memahami sifat umum suatu bidang kajian yang berkaitan dengan Automata.

Sedangkan otomata (Automata) adalah suatu sistem yang terdiri atas sejumlah berhingga state yang mempelajari tentang mesin abstrak yang menerima input dan mengeluarkan output dalam bentuk diskret (satu per satu). Dimana state adalah suatu kondisi yang menyatakan informasi mengenai input yang lalu sedangkan input pada otomata dianggap sebagai batas yang harus dikenali oleh mesin.
29 Juli 2009 17.50

Anonim mengatakan...
Nama : Indra Ade Mula Putra
NIM : 20094260


Teori otomata yang selama ini banyak diterapkan dalam bidang tata bahasa formal khususnya dalam sebuah pengembangan compiler, juga dapat digunakan untuk melakukan pemodelan atau pendekatan pemecahan masalah - masalah yang berkaitan dengan aplikasi didalam bidang kecerdasan buatan.

TEORI BAHASA & AUTOMATA

TEORI BAHASA & AUTOMATA

Teori Bahasa
Teori bahasa membicarakan bahasa formal (formal language), terutama untuk
kepentingan perancangan kompilator (compiler) dan pemroses naskah (text
processor). Bahasa formal adalah kumpulan kalimat. Semua kalimat dalam sebuah
bahasa dibangkitkan oleh sebuah tata bahasa (grammar) yang sama. Sebuah bahasa
formal bisa dibangkitkan oleh dua atau lebih tata bahasa berbeda. Dikatakan bahasa
formal karena grammar diciptakan mendahului pembangkitan setiap kalimatnya.
Bahasa manusia bersifat sebaliknya; grammar diciptakan untuk meresmikan kata-kata
yang hidup di masyarakat. Dalam pembicaraan selanjutnya ‘bahasa formal’ akan
disebut ‘bahasa’ saja.
Automata
Automata adalah mesin abstrak yang dapat mengenali (recognize), menerima
(accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu.
Automata berasal dari bahasa Yunani automatos, yang berarti sesuatu yang bekerja
secara otomatis (mesin).

Pengertian mesin bukan hanya mesin elektronis/mekanis saja melainkan segala sesuatu (termasuk perangkat lunak) yang memenuhi ketiga ciri di atas. Penggunaan automata pada perangkat lunak terutama pada pembuatan kompiler bahasa pemrograman. Secara garis besar ada dua fungsi automata dalam hubungannya dengan bahasa, yaitu :
• fungsi automata sebagai pengenal (RECOGNIZER) string-string dari suatu bahasa, dalam hal ini bahasa sebagai masukan dari automata
• fungsi automata sebagai pembangkit (GENERATOR) string-string dari suatu bahasa, dalam hal ini bahasa sebagai keluaran dari automata

Teknik Kompilasi

Teknik adalah suatu metode atau cara.

Kompilasi adalah suatu proses penggabungan serta menterjemahkan sesuatu (source program) menjadi bentuk lain.
Merupakan Teknik dalam melakukan pembacaan suatu program yang ditulis dalam bahasa sumber, kemudian diterjemahkan ke dalam suatu bahasa lain yang disebut bahasa sasaran. Dalam melakukan proses penerjemahan tersebut, sudah barang tentu kompilator akan melaporkan adanya keanehan-keanehan atau kesalahan yang mungkin ditemukannya. Proses penerjemahan yang dilakukan oleh kompilator ini disebut proses kompilasi (compiling).
Kompilator (compiler) adalah sebuah program yang membaca suatu program
yang ditulis dalam suatu bahasa sumber (source language) dan menterjemahkannya
ke dalam suatu bahasa sasaran (target language).

Proses kompilasi dapat digambarkan melalui sebuah kotak hitam (black box) berikut :
Program sumber                         kompilator                          Bahasa Sasaran

             Pesan-pesan  Kesalahan
                   (error messages)

Proses kompilasi:
-  Mulai dari jenis bahasa
-  Perancangan bahasa pemrograman
-  Translator
-  Proses kompilasi dari fase analisa (leksikal, sintaks, dan semantik) hingga ke fase sintesa (pembentukan dan optimalisasi kode)

Proses kompilasi dikelompokkan ke dalam dua kelompok besar :
1. analisa : program sumber dipecah-pecah dan dibentuk menjadi bentuk antara (intermediate
representation)
Secara umum proses dalam tahap analis terdiri dari 3 bagian utama, yaitu
1.  Proses analisis leksikal
2.  Proses analisis sintaktik
3.  Proses analisis semantik


2. sintesa : membangun program sasaran yang diinginkan dari bentuk antara
Untuk tahap sintetis terdiri dari 2 bagian utama, yaitu
1. Proses yang menghasilkan kode (code generator)
2. Proses optimasi kode (code optimizer)
Fase-fase proses sebuah kompilasi adalah sebagai berikut :
Program sumber


Penganalisa leksikal
(scanner)


Penganalisa sintaks
(parser)

Pengelola tabel simbol   Penganalisa semantik         Penanganan kesalahan

Pembangkit
kode antara


  Pengoptimal kode


Pembangkit kode


Bahasa sasaran

Program sumber merupakan rangkaian karakter. Berikut ini hal-hal yang dilakukan oleh
setiap fase pada proses kompilasi terhadap program sumber tersebut :

1. Penganalisa leksikal : membaca program sumber, karakter demi karakter. Sederetan
(satu atau lebih) karakter dikelompokkan menjadi satu kesatuan
mengacu kepada pola kesatuan kelompok karakter (token) yang
ditentukan dalam bahasa sumber. Kelompok karakter yang
membentuk sebuah token dinamakan lexeme untuk token
tersebut. Setiap token yang dihasilkan disimpan di dalam tabel
simbol. Sederetan karakter yang tidak mengikuti pola token
akan dilaporkan sebagai token tak dikenal (unidentified token).
Contoh : Misalnya pola token untuk identifier I adalah : I = huruf(hurufangka)*.
Lexeme ab2c dikenali sebagai token sementara lexeme 2abc atau abC tidak
dikenal.

2. Penganalisa sintaks : memeriksa kesesuaian pola deretan token dengan aturan sintaks
yang ditentukan dalam bahasa sumber. Sederetan token yang
tidak mengikuti aturan sintaks akan dilaporkan sebagai
kesalahan sintaks (sintax error). Secara logika deretan token
yang bersesuaian dengan sintaks tertentu akan dinyatakan
sebagai pohon parsing (parse tree).
Contoh : Misalnya sintaks untuk ekspresi if-then E adalah : E → if L then, L → IOA,
I = huruf(hurufangka)*, O → <=><=>=, A → 01...9. Ekspresi
if a2 < 9 then adalah ekspresi sesuai sintaks; sementara ekspresi if a2 < 9 do
atau if then a2B < 9 tidak sesuai. Perhatikan bahwa contoh ekspresi terakhir
juga mengandung token yang tidak dikenal.

3. Penganalisa semantik : memeriksa token dan ekspresi dari batasan-batasan yang
ditetapkan. Batasan-batasan tersebut misalnya :
a. panjang maksimum token identifier adalah 8 karakter,
b. panjang maksimum ekspresi tunggal adalah 80 karakter,
c. nilai bilangan bulat adalah -32768 s/d 32767,
d. operasi aritmatika harus melibatkan operan-operan yang
bertipe sama.

4. Pembangkit kode antara : membangkitkan kode antara (intermediate code) berdasarkan
pohon parsing. Pohon parse selanjutnya diterjemahkan
oleh suatu penerjemah yang dinamakan penerjemah
berdasarkan sintak (syntax-directed translator). Hasil
penerjemahan ini biasanya merupakan perintah tiga alamat
(three-address code) yang merupakan representasi program
untuk suatu mesin abstrak. Perintah tiga alamat bisa
berbentuk quadruples (op, arg1, arg2, result), tripels (op,
arg1, arg2). Ekspresi dengan satu argumen dinyatakan
dengan menetapkan arg2 dengan - (strip, dash)

5. Pengoptimal kode : melakukan optimasi (penghematan space dan waktu komputasi),
jika mungkin, terhadap kode antara.

6. Pembangkit kode : membangkitkan kode dalam bahasa target tertentu (misalnya
bahasa mesin).