TEORI BAHASA DAN AUTAMATA

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.

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.
• •Jika w adalah sebuah string maka panjang string dinyatakan sebagai w  dan didefinisikan sebagai cacahan (banyaknya) simbol yang menyusun string tersebut. Sebagai contoh, jika w = abcb maka w= 4.
• •String  hampa  adalah  sebuah  string  dengan  nol  buah  simbol.  String  hampa dinyatakan  dengan  simbol  å  (atau  ^)  sehingga  å=  0.  String  hampa  dapat dipandang sebagai simbol hampa karena keduanya tersusun dari nol buah simbol.
• •Alfabet adalah himpunan 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. Contoh : abc, ab, a, dan å adalah semua Prefix(x)
• •ProperPrefix  string  w  adalah  string  yang  dihasilkan  dari  string  w  dengan menghilangkan satu atau lebih simbol-simbol paling belakang dari string w tersebut. Contoh : ab, a, dan å adalah semua ProperPrefix(x)
• •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. Contoh : abc, bc, c, dan å adalah semua Postfix(x)
• •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. Contoh : bc, c, dan å adalah semua ProperPostfix(x)
• • Head string w adalah simbol paling depan dari string w. Contoh : a adalah Head(x)

• Tail string w adalah string yang dihasilkan dari string w dengan menghilangkan simbol paling depan dari string w tersebut. Contoh : bc adalah Tail(x)
• •Substring   string   w  adalah   string   yang   dihasilkan   dari   string   w  dengan menghilangkan nol atau lebih simbol-simbol paling depan dan/atau simbol-simbol paling belakang dari string w tersebut. Contoh : abc, ab, bc, a, b, c, dan å adalah semua Substring(x)
• •ProperSubstring  string  w adalah  string  yang  dihasilkan dari  string  w dengan menghilangkan  satu  atau  lebih  simbol-simbol  paling  depan  dan/atau  simbol- simbol paling belakang dari string w tersebut. Contoh : ab, bc, a, b, c, dan å adalah semua Substring(x)
• •Subsequence  string  w  adalah  string  yang  dihasilkan  dari  string  w  dengan menghilangkan nol atau lebih simbol-simbol dari string w tersebut. Contoh : abc, ab, bc, ac, a, b, c, dan å adalah semua Subsequence(x)
• •ProperSubsequence string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atau lebih simbol-simbol dari string w tersebut. Contoh : ab, bc, ac, a, b, c, dan å adalah semua Subsequence(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 atau 123
• •Kleene Closure : x* = åxxxxxx… = åxx 2 x 3 …
• •Positive Closure : x +  = xxxxxx… = xx 2 x 3 …

Selengkapnya Silahkan Buka di Link

http://adf.ly/12482271/teori-bahasa-dan-autamata