Teori Bahasa & Otomata

Konsep Teori Bahasa dan Otomata

Teori bahasa dan otomata merupakan salah satu mata kuliah yang wajib di jurusan[1]jurusan teknik informatika maupun ilmu komputer. Teori bahasa dan otomata merupakan mata kuliah yang cenderung bersifat teoritis tidak memuat hal-hal yang ‘praktis’ untuk diterapkan langsung dalam praktik. Manfaat langsung dari mata kuliah teori bahasa dan otomata akan kita dapatkan ketika mempelajari mata kuliah Teknik Kompilasi.

Bahasa di dalam kamus adalah suatu sistem yang meliputi pengekspresian gagasan, fakta, konsep, termasuk sekumpulan simbol-simbol dan aturan untuk melakukan manipulasinya. Bahasa bisa juga disebut sebagai rangkaian simbol-simbol yang mempunyai makna.

Otomata merupakan suatu sistem yang terdiri atas sejumlah berhingga state, di mana state menyatakan informasi mengenai input. Otomata juga dianggap sebagai mesin otomatis (bukan mesin fisik) yang merupakan suatu model matematika dari suatu sistem yang menerima input dan menghasilkan output, serta terdiri dari sejumlah berhingga state.

Hubungan di antara bahasa dan otomata adalah bahasa dijadikan sebagai input oleh suatu mesin otomata, selanjutnya mesin otomata akan membuat keputusan yang mengindikasikan apakah input itu diterima atau tidak.

Misalnya, kita memiliki sebuah mesin sederhana yang menerima input kata dalam bahasa Indonesia, hal ini bisa dilihat pada gambar berikut ini. 

Pada gambar di atas, bila mesin mendapat string input berikut.

1. ada : diterima

2. adu : diterima

3. add : ditolak

sebuah string input diterima bila mencapai state akhir / final state yang disana digambarkan dengan lingkaran ganda. Mesin ini memiliki 6 state, {q0,q1,q2,q3,q4,q5}, yang mana adalah himpunan state yand ada pada mesin itu. State awal dari mesin adalah q0. {q3,q4} adalah himpunan state akhir/final. Sedangkan himpunan simbol input adalah {a,d,u}.

Hirarki Chomsky

Tata bahasa (grammar) bisa didefinisikan secara formal sebagai kumpulan dari himpunan-himpunan variabel, simbol-simbol terminal, simbol awal, yang dibatasi oleh aturan-aturan produksi. Pada tahun 1959, seorang ahli bernama Noam Chomsky melakukan penggolongan tingkatan bahasa menjadi empat, yang disebut dengan hirarki Chomsky.

 Penggolongan tersebut bisa dilihat pada tabel berikut.

Secara umum tata bahasa dirumuskan sebagai :

α → β, yang berarti α menghasilkan β atau α menurunkan β.

Di mana α menyatakan simbol-simbol pada ruas kiri aturan produksi (sebelah kiri tanda

‘→’) dan β menyatakan simbol-simbol pada ruas kanan aturan produksi (sebelah kanan

tanda ‘→’)

 

Simbol variabel / non terminal adalah simbol yang masih bisa diturunkan dan ditandai

dengan huruf besar seperti A, B, C, dst.

 

Simbol terminal adalah simbol yang sudah tidak bisa diturunkan dan ditandai dengan

huruf kecil seperti a, b, c, dst.

Contoh :

A → b (Diterima)

a → B (Ditolak, karena simbol pada sebelah kiri harus berupa sebuah simbol variabel)

A → B (Diterima)

A → bC (Diterima)

A → Bc (Ditolak, karena simbol variabel pada sebelah kanan harus berada pada posisi

paling kanan)

A → bcD (Diterima)

A → bCD (Ditolak, karena simbol pada sebelah kanan maksimal hanya memiliki sebuah

simbol variabel)

Ab → c (Ditolak, karena simbol pada sebelah kiri harus berupa sebuah simbol variabel)

 

Tentukan apakah produksi-produksi berikut memenuhi aturan tata bahasa Regular

1. A → b

2. B → bdB

3. B → C

4. B → bC

5. B → Ad

6. B → bcdef

7. B → bcdefg

8. A → aSa

9. A → aSS

10. A → є

11. Ad → dB

Contoh :

A → b (Diterima)

A → B (Diterima)

A → bC (Diterima)

A → Bc (Diterima)

A → BcD (Diterima)

A → AAA (Diterima)

a → b (Ditolak, karena simbol pada sebelah kiri harus berupa sebuah simbol variabel)

Ab → c (Ditolak, karena simbol pada sebelah kiri harus berupa sebuah simbol

variabel)

AB → c (Ditolak, karena simbol pada sebelah kiri harus berupa sebuah simbol

variabel)

 

Tentukan apakah aturan produksi-produksi berikut memenuhi aturan tata bahasa

bebas konteks.

1. A → aSa

2. A → Ace

3. A → ab

4. A → є

5. B → bcdef

6. B → bcdefG

7. A → aSa

8. A → aSS

9. A → BCDEF

10. Ad → dB

11. A → AAAAA

12. d → A

Contoh :

A → bc (Diterima)

Ab → cd (Diterima)

AB → CD (Diterima)

ABC → DE (Ditolak, karena jumlah simbol pada ruas sebelah kiri lebih bayak dari

jumlah simbol pada ruas kanan)

Ab → cDe (Diterima)

bA → cd (Diterima)

a → b (Ditolak, karena simbol pada sebelah kiri harus minimal ada sebuah simbol

variabel)

 

Tentukan apakah produksi-produksi berikut memenuhi aturan tata bahasa context

sensitive.

1. B → bcdefG

2. A → aSa

3. A → aSS

4. A → BCDEF

5. Ad → dB

6. A → є

7. AB → є

8. ad → b

9. ad → є

10. abC → DE

11. abcDef → ghijkl

12. AB → cde

13. AAA → BBB

Contoh :

Abcdef → g (Diterima)

aBCdE → GHIJKL (Diterima)

abcdef → GHIJKL (Ditolak, karena simbol pada sebelah kiri tidak ada sebuah simbol

variabel)

 

Tentukan apakah produksi-produksi berikut memenuhi aturan tata bahasa unrestricted.

1. A → є

2. AB → є

3. ad → b

4. ad → є

5. abC → DE

6. AB → cde

7. e → a

8. ABCDEFG → h

9. bA → CDEFGH