Blog Teori Bahasa Dan Otomata DI Sertai HIRARKI CHOMSKY || MuhammadTegarWiratamaPohan_ 2021311169

HIRARKI CHOMSKY

    Tata Bahasa (grammar) didefinisikan sebagai kumpulan dari himpunan-himpunan variable, simbol-simbol terminal, simbol awal yang dibatasi oleh aturan produksi. Pada tahun 1959, Noam Chomsky menggolongkan tingkatan bahasa menjadi empat yang disebut sebagai Hirarki Chomsky. Penggolongan Hirarki Chomsky

Tabel 1.0 Penggolongan Bahasa

o   Tipe 0 / Unrestricted / Natural Language

Aturan :

• Simbol pada ruas sebelah kiri harus minimal ada sebuah simbol variabel.
• Tidak ada batasan pada aturan produksinya.

Contoh :

Abc => De (diterima)

ABC => b (diterima)

abc => GHI (ditolak, karena simbol pada sebelah kiri tidak ada sebuah simbol variabel)

o   Tipe 1 / Konteks Sensitive

Aturan :

• Simbol pada ruas sebelah kiri harus minimal ada sebuah simbol variabel.
• Panjang string pada ruas kiri <= panjang string pada ruas kanan. |ɑ| <= |β|.

Contoh :

Ab => DeF (diterima)

CD => eF (diterima)           exception : S => ɛ (diterima)

ABC => DE (ditolak, karena jumlah simbol pada ruas sebelah kiri lebih banyak dari jumlah simbol pada ruas kanan)

o   Tipe 2 / Bebas Konteks / Context Free

Aturan :

• Simbol pada sebelah kiri harus berupa sebuah simbol variable

      Contoh :

B => CDeFG (diterima)

D => BcDe (diterima)

a => b (ditolak, karena simbol pada sebelah kiri harus berupa sebuah simbol variabel)

o   Tipe 3 / Reguler Aturan

Aturan :

• Simbol pada sebelah kiri harus berupa sebuah simbol variable
• Simbol pada sebelah kanan maksimal hanya memiliki sebuah simbol variabel dan bila ada terletak di posisi paling kanan.

      Contoh :

A => e (diterima)

A => fgh (diterima)

A => eH (diterima)

C => D (diterima)

A => Bc (ditolak, karena simbol variabel pada sebelah kanan harus berada pada posisi paling kanan

 

Bahasa	Mesin Otomata	Batasan Aturan Produksi
Regular/Tipe 3	Finite State Automata (FSA) : 1.     Deterministic            Finite Automata (DFA) 2.     Non- Deterministic Finite Automata (NFA)	α merupakan sebuah simbol variable β maksimal memiliki sebuah simbol variable yang bila ada terletak diposisi paling kanan

Bahasa	Mesin Otomata	Batasan Aturan Produksi
Bebas             Konteks/Context Free/Tipe2	Push Down Automata (PDA)	α       berupa sebuah   simbol variable
Context Sensitive/Tipe1	Linier Bounded Automata	|α | ≤ |β|
Unrestricted/Phase Structure/Natural Language/Tipe 0	Mesin Turing	Tidak ada batasan

 

Aturan produksi merupakan pusat dari tata bahasa yang menspesifikasikan bagaimana suatu tata bahasa melakukan transformasi dari suatu string ke bentuk lainnya dan melalui aturan produksi tersebut didefinisikan suatu bahasa yang berhubungan dengan tata bahasa tersebut. Suatu aturan produksi dapat dinyatakan dalam bentuk α→β ( dibaca : α menghasilkan β atau dibaca : α menurunkan β). Suatu α menyatakan simbol-simbol pada ruas kiri aturan produksi. Sedangkan β menyatakan simbol-simbol pada ruas kanan aturan produksi. Beberapa istilah dalam aturan produksi :

1.     Simbol variable/nonterminal : simbol yang masih dapat diturunkan, biasanya dilambangkan menggunakan abjad capital.

2.     Simbol terminal                      : simbol yang tidak dapat diturunkan kembali, biasanya dilambangkan menggunakan abjad non-capital(huruf kecil).

Contoh penerapan tata bahasa “Noam Chomsky” :

Table 2.0 Contoh Tata Bahasa Berdasarkan Penggolongan Noam Chomsky

 

Bahasa	Contoh
Regular/Tipe 3	A → b
Bebas Konteks/Context Free/Tipe2	B → bcA
Context Sensitive/Tipe1	B → Abcd
Unrestricted/Phase   Structure/Natural Language/Tipe 0	AbC → abC

A. DETERMINISTIC FINITE AUTOMATA / DFA

Deterministic Finite Automata merupakan bagian dari FSA. Deterministic Finite Automata/DFA maksudnya dari suatu state ada tepat satu state berikutnya untuk setiap simbol masukan yang diterima. Contohnya :

•        Q = {q0,q1,q2}

•          ∑ = {a,b}

•          S = q0

•        F = {q2}

 

 

Suatu fungsi transisi bisa di bentuk menjadi 2 bentuk :

					δ a b q0 {q0} {q1} q1 {q1} {q2} q2 {q1} {q2}

B.     NON-DETERMINISTIC FINITE AUTOMATA / NFA

Non-Deterministic Finite Automata merupakan bagian dari FSA. Non-Deterministic Finite Automata/NFA maksudnya Dari suatu state bisa terdapat 0, 1 atau lebih busur keluar (transisi) berlabel simbol input yang sama. Contohnya :

•        Q = {q0,q2}

•          ∑ = {a,b}

•          S = q0

•         

F = {q2}

	δ a b q0 {q0,q2} {q2} q2 {q2} {q2}

Dari state q0 ketika memperoleh inputan yang sama yaitu a

dapat menuju ke lebih dari 1 state yaitu {q0,q2}