teori komputasi

NAMA            : ANDI BAHARUDDIN

NIM                : H11111251

TUGAS TEORI KOMPUTASI

Teori Bahasa adalah konsep-konsep pada "string alpabet “ dalam penyambungan karakter-karakter alpabet untuk membentuk suatu makna (bahasa).

Alpabet  adalah himpunan simbol (karakter) tak        kosong yang  berhingga. Alpabet digunakan untuk membentuk kata-kata (string-string) di bahasa. Bahasa dimulai dengan alpabet. Alpabet dilambangkan dengan Σ.

String adalah deretan simbol dari alpabet dimana perulangan simbol diijinkan.
Contoh :
V = {a,b,c,d}
String pada alpabet V antara lain -> 'a','abcd','bbba'

panjang string adalah jumlah simbol di dalam string bukan pada alpabet dan pengulangan kemunculan simbol dihitung. Panjang string dilambangkan |w| .

            Contoh:
            |ε| = 0
            |a| = 1
            |aa| = 2
            |aaa| = 3
            |aaab| = 4

Empty  string(null string) adalah string yang tidak mengandung simbol apapun. Lambangnya e atau l.

Regular expression adalah cara untuk mengekspresikan bahasa dengan hanya menggunakan operasi :

•      Concatenation

•      Superscript

•      Kleene closure

•      Positif closure

Penyambungan (Concatenation - o)
Penyambungan dilakukan pada 2 karakter atau lebih membentuk 1 barisan karakter (string simbol).

Contoh :
'a' o 'b' = 'ab'
'ab' o 'baab' = 'abbaab'

Kleene closure

V^* = {ε} U V⁺ adalah string pada V, termasuk string kosong dimana ε string kosong (string tanpa simbol)
ε mempunyai sifat identitas, yaitu:
ε o x = x
x o ε = x

Positive closure

V⁺ = V¹ U V² U V³ U ...
adalah himpunan string pada V, tidak ada string kosong didalamnya.V⁰ = {ε}
adalah himpunan yang isinya hanya string kosong, dimana String kosong ε tidak sama dengan himpunan kosong .

Tata bahasa (grammar) bisa didefinisikan secara formal sebagai kumpulan dari himpunan-himpunan variabel, simbol-simbol terminal, simbol awal yang dibatasi oleh aturan-aturan produksi.

Contoh :

 G₁ :  V_T = {I,  Love, Miss, You}, V = {S,A,B,C},

                        P = {S ® ABC, A® I, B® Love | Miss, C® You}

S Þ ABC

   Þ IloveYou

L(G1)={IloveYou, IMissYou}

Aturan produksi merupakan pusat dari tata bahasa, yang menspesifikasikan bagaimana suatu tata bahasa melakukan transformasi suatu string ke bentuk lainnya.

Penggolongan empat tingkatan bahasa berdasarkan hirarki Comsky dapat dilihat pada tabel berikut :

Bahasa	Mesin Otomata	Batasan Aturan Produksi.
Reguler Type 3	Finite State Automata, meliputi : •       DFA •       NFA	α adalah sebuah simbol variabel. β maksimal memiliki sebuah simbol variabel yang bila ada terletak di posisi paling kanan, boleh tidak ada.
Bebas Konteks (Context Free) Tipe 2	Push Down Automata	α adalah sebuah simbol variabel.
Context Sensitive Tipe1	Linier Bounded Automata	|α | ≤ |β|
Unrestricted (Phase Structure) Natural Language Tipe 0	Mesin Turing	Tidak ada batasan.

•      Otomata hingga adalah suatu model yang dapat diterapkan pada beragam jenis perangkat keras (hardware) dan perangkat lunak (software).

•      Penerapan-penerapan dari otomata hingga adalah:

q  Perangkat lunak yang digunakan untuk merancang dan memantau perilaku rangkaian digital.

q  Lexical Analyzer, yaitu komponen kompiler yang bertugas memecah teks-teks input menjadi logical unit seperti identifiers, keyword dan punctuation.

q  Perangkat lunak untuk memindai dokumen teks yang jumlah halamannya luar biasa banyak guna menemukan kesamaan kata, frase dan bentuk-bentuk lain

q  Perangkat lunak yang digunakan untuk memeriksa sistem-sistem dengan stata/state berbeda yang berhingga jumlahnya, misalnya protokol komunikasi atau protokol yang digunakan untuk pertukaran informasi secara aman.

FINITE STATE AUTOMATA (FSA)

·         FSA didefinisikan sebagai pasangan 5 tupel : (Q, ∑, δ, S, F).

Q : himpunan hingga state

∑ : himpunan hingga simbol input (alfabet)

δ : fungsi transisi, menggambarkan transisi state FSA akibat pembacaan simbol input.

       Fungsi transisi ini biasanya diberikan dalam bentuk tabel.

S Î Q : state AWAL

F Ì Q : himpunan state AKHIR

Contoh : FSA untuk mengecek parity ganjil

Q ={Gnp, Gjl}                                          diagram transisi

∑ = {0,1}

tabel transisi

δ	0	1
Gnp	Gnp	Gjl
Gjl	Gjl	Gnp

S = Gnp, F = {Gjl}

Ada dua jenis FSA :

·               Deterministic finite automata (DFA)

·               Non deterministik finite automata.(NFA)

-       DFA : transisi state FSA akibat pembacaan sebuah simbol bersifat tertentu.

                                δ  : Q ´ ∑® Q

-       NFA : transisi state FSA akibat pembacaan sebuah simbol bersifat tak tentu.

                    δ : Q ´ ∑ ® 2^Q