Pengantar Teori Bahasa dan Automata

PENGANTAR TEORI BAHASA DAN AUTOMATA 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. Bahasa Formal adalah suatu kalimat yang dibentuk dengan menerapkan serangkaian aturan produksi pada sebuah simbol “akar”. Proses penerapan aturan produksi dapat digambarkan sebagai suatu diagram pohon.

Credits: Ahwan0m.site

Automata


Automata adalah mesin abstrak yang dapat mengenali (recognize), menerima (accept), atau membangkitkan (generate) sebuah kalimat dalam bahasa tertentu. Teori Automata : studi tentang komputasi abstrak sebuah perangkat berbasis komputer atau mesin. 

Sebelum adanya komputer (1930), Alan Turing mempelajari sebuah mesin abstrak (Turing machine) yang memiliki semua kapabilitas yang dimiliki oleh sebuah komputer yang ada sekarang (tergantung pada pemakaiannya). Tujuannya adalah menggambarkan secara jelas batasan antara apa yang dapat dilakukan oleh sebuah mesin berbasis komputer dan apa yang tidak.

Beberapa contoh tipe mesin (finite automata) yang dipelajari oleh sejumlah peneliti dan berguna untuk berbagai macam keperluan. Dalam dunia matematika, automata berkaitan dengan teori mesin abstrak, yaitu mesin sekuensial yang menerima input dan mengeluarkan output, dalam bentuk diskrit.

Tujuan Mempelajari Teori Bahasa dan Otomata

Credits: Teknoiot

1. Regular Expression digunakan dalam berbagai sistem seperti : UNIX (a.*b), XML tags dengan format RE (person (name, addr, child*) )

2. Finite Automata Model Protocol , rangkaian elektronik ; teori digunakan untuk model-checking.

3. Contex-free Grammar digunakan untuk mendeskripsikan sintaks pada hampir seluruh bahasa pemrograman


Dasar-dasar Teori Bahasa Automata

A. Alphabet

Alphabet adalah simbol-simbol yang tidak kosong (nonempty) dan terbatas. Simbol adalah sebuah entitas abstrak (seperti halnya pengertian titik dalam geometri). Sebuah huruf atau sebuah angka adalah contoh simbol. Simbol : ∑

Contoh:

Alphabet binary : ∑ = {0, 1}

Set dari semua huruf-huruf kecil : ∑ = {a, b, . . . , z}

Set dari semua karakter ASCII

B. String


Sebuah string (atau kadang disebut sebuah word) adalah deretan terbatas dari simbol-simbol terpilih dari sejumlah alphabet Contoh: 01101 dan 111 adalah string dari alphabet binari ∑ = {0, 1}

String hampa (null string)adalah sebuah string dengan nol kemunculan simbol. String hampa dinyatakan dengan simbol e (atau ^ ) sehingga |e| = 0. String hampa dapat dipandang sebagai simbol hampa karena keduanya tersusun dari nol buah simbol. Panjang sebuah string: jumlah posisi simbol dalam sebuah string

Contoh : 01101 memiliki panjang 5. Meskipun hanya ada dua simbol (0 dan 1) dalam string 01101, tetapi 5 posisi untuk simbol.


Notasi panjang w : | w |

Contoh: | 011 | = 3 dan l e l = 0

Jika ∑ adalah sebuah alphabet, kita dapat mengekspresikan sebuah set dari sejumlah string dengan panjang tertentu dari alphabet tersebut dengan menggunakan notasi eksponensial :

∑k : sebuah set string dengan panjang k, dengan setiap komponen simbol di dalamnya.

Contoh:

∑ 0 : {e}, tanpa memperhitungkan alphabet apapun di dalamnya. Hanya e yang merupakan string dengan panjang 0.

Jika ∑ = {0, 1}, then:

1. ∑ 1 = {0, 1}

2. ∑ 2 = {00, 01, 10, 11}

3. ∑ 3 = {000, 001, 010, 011, 100, 101, 110, 111}



Catatan : Penjelasan ∑ dan ∑ 1:

1. ∑ adalah sebuah alphabet; anggotanya adalah 0 and 1 yang merupakan simbol.

2. ∑ 1 adalah sebuah string; anggotanya adalah string yang masing-masing memiliki panjang 1.

C. Kleen Closure dan Positive Closure


Kleene Closure :

X* = e | x | xx | xxx | … = e | x | x2 | x3 |

Positive Closure :

 x + = x | xx | xxx | … = x | x2 | x3 |

∑* : Sebuah set dari semua string yang terbentuk dari sekelompok

alphabet.

{0, 1}* = {e, 0, 1, 00, 01, 10, 11, 000, . . .}
∑* = ∑0 ∪ ∑1 ∪ ∑2 ∪ . . .

Simbol ∑ * disebut Kleene star dan diberi nama berdasarkan nama ahli matematika dan logika Stephen Cole Kleene.

∑ + = ∑1 ∪ ∑2 ∪ . . .

sehingga ∑ *: = ∑ + ∪ {e}

D. Concatenation


Definisikan operasi biner yang disebut concatenation pada ∑* berikut ini :

Jika a1a2a3 . . . an dan b1b2 . . . bm adalah bagian ∑* ,

maka a1a2a3 . . . an.b1b2 . . . bm = a1a2a3 . . . anb1b2 . . . bm

Dapat dikatakan, sejumlah string dapat di-concatenate dengan string yang lain Jika x dan y membentuk string maka x.y menyatakan concatenation dari x dan y, yaitu string yang terbentuk dari tiruan x dan diikuti oleh tiruan y

Contoh:

1. x = 01101 and y = 110

Maka xy = 01101110 dan yx = 11001101

2. Untuk setiap string w, persamaan e w = w e = w .

Persamaan ini , e adalah identitas untuk concatenation

Jika S dan T adalah subsets dari ∑* , maka

S.T = {s.t | s ∈ S, t ∈ T}

Concatenation adalah penyambungan dua buah string. Operator Concatenation adalah concate atau tanpa lambang apapun. Contoh : concate (xy) = xy = abc123, Alternation adalah pilihan satu diantara dua buah string. Operator alternation adalah alternate atau | . Contoh alternate (xy) = x | y = abc atau 123

Operasi Dasar String


Diberikan dua string : x = abc, dan y = 123
  • Prefix 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 e adalah semua prefix (x).
  • ProperPrefix string w adalah string yang dihasilkan dari string w denganmenghilangkan satu atau lebih simbol-simbol paling belakang dari string w tersebut.
          Contoh : ab,a, dan e 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 e adalah semua Postfix (x).
  • ProperPostfix (atau ProperSufix) 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 e 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 e 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 e adalah semua ProperSubstring (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 e adalah semua Sub sequence (x).
  • ProperSubsequence string w adalah string yang dihasilkan dari string w dengan menghilangkan satu atu lebih simbol-simbol dari string w tersebut.
          Contoh : ab, bc, ac,a,b,c dan e adalah semua ProperSubsequence (x)

Tidak selalu berlaku : x= Prefix(x)Postfix(x)

Selalu berlaku : x = Head(x)Tail(x)

Tidak selalu berlaku : Prefix(x) = Postfix(x) atau Prefix(x) ¹ Postfix (x)

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.

Setiap Substring(x) adalah Subsequence(x), tetapi tidak sebaliknya.

Sifat Aljabar Concatenation


Operasi concatenation bersifat asosiatif :

x ( y z ) = ( x y ) z

Elemen identitas operasi concatenation adalah e : ex = xe = x

Tiga sifat aljabar alternation :

Operasi alternation bersifat komutatif : x | y = y | x

Operasi alternation bersifat asosiatif :

x | ( y | z ) = ( x | y ) | z

Elemen identitas operasi alternation adalah dirinya sendiri : x | x = x

Sifat distributif concatenation terhadap alternation : x ( y | z) = xy | xz

Beberapa kesamaan :

Kesamaan ke-1 : (x * ) * = (x * )
Kesamaan ke-2 : e | x+ = x+ | e = x *
Kesamaan ke-3 : ( x| y )* = e | x | y | xx | yy | xy | yx | … =   semua string yang merupakan concatenation dari nol atau lebih x, y, atau keduanya.

BAHASA


Jika ∑ adalah sebuah alphabet, dan L ⊆ ∑* , maka L adalah sebuah (formal) bahasa pada ∑. Bahasa (Language): sebuah set dari string (kemungkinan tidak terbatas) yang komponennya dipilih dari beberapa ∑*. Sebuah bahasa pada ∑ boleh tidak mengikutkan semua string dengan semua symbol pada ∑. Maka, sebuah bahasa pada ∑ juga merupakan sebuah bahasa pada setiap alphabet yang merupakan superset dari ∑

Contoh:

• Bahasa Pemrograman C

Program-program yang legal adalah sebuah subset dari semua string yang mungkin dapat dibentuk dari alphabet sebuah bahasa (sebuah subset dari karakter ASCII)

• Bahasa Inggris atau Bahasa Perancis

Contoh Bahasa

1. Sebuah bahasa dari semua strings yang terdiri dari n buah 0 diikuti oleh n buah 1 (n ≥ 0): {e, 01, 0011, 000111, . . .}

2. Sebuah set dari strings terdiri dari sejumlah 0 dan 1 dengan jumlah yang sama : {e, 01, 10, 0011, 0101, 1001, . . .}

3. ∑* adalah sebuah bahasa untuk setiap alphabet ∑

4. ∅, adalah bahasa hampa (empty language), adalah sebuah bahasa untuk setiap alphabet

5. {e}, bahasa yang terdiri dari hanya string hampa (empty string), juga merupakan bahasa untuk setiap alphabet. Catatan : ∅ ≠ {e} karena ∅ tidak memiliki strings dan {e} memiliki satu string

6. {w | w terdiri dari sejumlah yang sama 0 dan 1}

7. {0 n1 n | n ≥ 1}

8. {0 I 1 j | 0 ≤ i ≤ j}

Beberapa Operator Penting dalam Bahasa

UNION

Union dari dua buah bahasa (languages) L dan M, dinotasikan dengan L ∪ M, adalah sebuah set dari strings yang didalamnya terdiri dari salah satu L, atau M, atau keduanya.

Contoh :
Jika L = {001, 10, 111} dan M = {e, 001} maka
L ∪ M = {e, 001, 10, 111}

CONCATENATION


Concatenation dari bahasa (languages) L dan M, dinotasikan dengan L . M atau hanya LM , adalah sebuah set dari strings yang dapat dibentuk dengan mengambil string yang manapun dalam L dan menggabungkannya dengan string apapun dalam M

Contoh :
Jika L = {001, 10, 111} dan M = {e, 001} maka
L.M = {001, 10, 111, 001001, 10001, 111001}

CLOSURE

Jika closure dari sebuah bahasa (language) L dinotasikan dengan L* dan merepresentasikan sebuah set dari sejumlah strings yang dapat dibentuk dengan mengambil sejumlah strings dari L, mungkin dengan repetisi (i.e., string yang sama dapat dipilih lebih dari sekali) dan menggabungkannya.

Contoh:

Jika L = {0, 1} maka L* adalah semua string dengan 0 dan 1

Jika L = {0, 11} maka L* terdiri dari string-string 0 dan 1 dimana 1 muncul secara berpasangan, e.g., 011, 11110 dan e. Tetapi bukan 01011 atau 101
Loading...

0 Response to "Pengantar Teori Bahasa dan Automata"

Post a Comment

Iklan Atas Artikel

Iklan Tengah Artikel 1

Iklan Tengah Artikel 2

Iklan Bawah Artikel