Caeyoooo Blogs

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)

1. State adalah suatu kondisi yang menyatakan informasi mengenai input yang lalu.
2. State dianggap sebagai memori mesin.
3. Input pada otomata dianggap sebagai batas yang harus dikenali oleh mesin

Teori Otomata dan bahasa formal, berkaitan dalam hal :

• Pembangkitan kalimat/generation : menghasilkan semuakalimat dalam bahasa L berdasarkan aturan yang dimilikinya
• Pengenalan kalimat / recognition: menentukan suatu string (kalimat) termasuk sebagai salah satu anggota himpunan L

Beberapa Sifat Operasi

1. Tidak selalu berlaku : x= Prefix(x)Postfix(x)
2. Selalu berlaku : x= Head(x)Tail(x)
3. Tidak selalu berlaku : Prefix(x) = Postfix(x) atau Prefix(x) Postfix(x)
4. Selalu berlaku :

ProperPrefix(x) ProperPostfix(x)

• Selalu berlaku : Head(x) Tail(x)
• Setiap Prefix(x), ProperPrefix(x), Postfix(x), ProperPostfix(x), Head(x), dan Tail(x) adalah Substring(x), tetapi tidak sebaliknya.

Operasi Dasar String
Diberikan dua string : x= abc, dan y= 123

• Prefik string wadalah string yang dihasilkan dari string wdengan menghilangkan nol atau lebih simbol-simbol paling belakang dari string w tersebut.

Contoh : abc, ab, a, dan adalah semua Prefix(x)

• ProperPrefix string w adalah string yang dihasilkan dari string wdengan menghilangkan satu atau lebih simbol-simbol paling belakang dari string w tersebut.

Contoh : ab, a, dan adalah semua ProperPrefix(x)

• Postfix (atau Sufix) string wadalah string yang dihasilkan dari string wdengan menghilangkan nol atau lebih simbol-simbol paling depan dari string wtersebut.
• ProperSubstring string wadalah string yang dihasilkan dari string wdengan menghilangkan satu atau lebih simbol-simbol paling depan dan/atau simbol-simbol paling belakang dari string wtersebut.

Contoh : ab, bc, a, b,c, dan adalah semua Substring(x)

• Subsequence string wadalah string yang dihasilkan dari string wdengan menghilangkan nol atau lebih simbol-simbol dari string wtersebut.

Contoh : abc,ab, bc, ac, a, b,c, dan adalah semua Subsequence(x)

• ProperSubsequence string wadalah string yang dihasilkan dari string wdengan menghilangkan satu atau lebih simbol-simbol dari string wtersebut.

Contoh : ab, bc, ac, a, b,c, dan adalah semuaSubsequence(x)


Concatenation adalah penyambungan dua buah string. Operator concatenation adalah concate atau tanpa lambang apapun
Contoh : concate(xy) = xy = abc123

• Alternation adalah pilihan satu di antara dua buah string. Operator alternation adalah alternate atau 

Contoh : alternate(xy) = xy = abc atau123

• Kleene Closure : x* = xxxxxx… = xxx…
• Positive Closure : x= xxxxxx… = xxx…