Bahasa dan Otomata
Bahasa Formal adalah kumpulan kalimat (grammar)
Otomata (automata)
Adalah mesin abstrak yg dapat:
-mengenali (Recognize)
-menerima (Accept)
-Membangkitkan (generate)
Sebuah kalimat dalam bahasa tertentu.
Beberapa pengertian dasar:
-simbol adalah :enititas yg abstrak ex:Angka dan huruf
-string adalah :deretan terbatas (finite) simbol
Ex:3 buah simbol a,b,c
Bisa menjadi :aabbcc,bisa acbb,aabc dll.
-string hampa adalah :string dg nol buah simbol yg dinyatakan dg simbol ∑ atau (^)
-alfabet adalah himpunan hingga (finite set) simbol-simbol2
OPERASI DASAR HITUNG
Diberikan 2 string ex: x=abc
Dan y=123
· Prefik string :string yg dihasilkan dari W dg menghilangkan nol atau lebih simbol2 paling belakang dari string w
Hasil abc,ab,a ..prefik (x)
Proper Prefik ,menghilangkan satu atau atau lebih simbol paling belakang
Ab,a, ..proper prefik (x)
· Postfix string(sufix)
Hasil :abc,bc,c
· Proper postfix
Ex:bc,c
· Head string w ex:simbol paling depan dari string w contoh :a, a adalah (x)
· Tail string :menghilangkan simbol paling depan
Ex:bc adalah tail string (x)
· Concatenitaion, penyambungan/penggabungan 2 buah string
Concat (x dan y)= abc123
· Alternation ,pilih salah satu dari 2 string Alternatif (xy)=x/y hasil abc atau 123
· Substring :menghilangkan o atau lebih simbol yg depan atau yg belakang
Hasil :abc,ab,bc,a,b,c
· Subsquance :menghilangkan o atau lebih simbol dari string
Hasil :abc,ab,bc,ac,a,b,c
