Tugas TBO pengganti kuliah (STIMIK AMIKOM)

Soal 1

Transformasikan CFG kedalam bentuk normal Chomsky:

S → aSb | ab

Soal 2

Transformasikan kedalam bentuk normal Chomsky:

S → aSaA | A
A → abA | b

Soal 3

Transformasikan kedalam bentuk normal Chomsky:

S → AA | C | bd
A → Bb
B → B | AB | d
C → de

Lakukan penyederhanaan terlibh dahulu bila perlu

Soal 4

Transformasikan kedalam bentuk normal Chomsky:

S → AB | CA
A → BC | AB
A → a
C → aB | b

Lakukan penyederhanaan terlibih dahulu bila perlu

Materi  dapat dilihat disini: Bentuk Normal Chomsky

Bentuk Normal Chomsky

Pengertian Bentuk Normal Chomsky

Bentuk normal Chomsky / Chomsky Normal Form  (CNF) merupakan salah satu bentuk normal yang sangat berguna untuk Context Free Grammar (CFG) . Bentuk normal Chomsky dapat dibuat dari sebuah tata bahasa bebas konteks yang telah mengalami penyederhanaan yaitu penghilangan produksi useless, unit, dan ε. Dengan kata lain, suatu tata bahasa bebas konteks dapat dibuat menjadi bentuk normal Chomsky dengan syarat tata bahasa bebas kontesk tersebut:

• Tidak memiliki produksi useless
• Tidak memiliki produksi unit
• Tidak memiliki produksi ε

Bentuk normal Chomsky (Chomsky Normal Form, CNF) adalah Context Free Grammar (CFG) dengan setiap produksinya berbentuk :

 A → BC atau A → a.

Transformasi CFG ke CNF

Transformasi CFG ke CNF adalah transformasi berikut :

Transformasi CFG ke CNF

Aturan produksi dalam  bentuk normal Chomsky ruas kanannya tepat berupa sebuah terminal atau dua variabel.

Misalkan:

• A → BC
• A → b
• B → a
• C → BA | d

Penyederhanaan Context Free Grammar (CFG)

Penyederhanaan Context Free Grammar (CFG)bertujuan untuk melakukan pembatasan sehingga tidak menghasilkan pohon penurunan yang memiliki kerumitan yang tak perlu atau aturan produksi tak berarti.

Missal :

• S → AB | a
• A → a

Kelemahanya adalah aturan produksi S → AB tidak berarti karena B tidak memiliki penurunan.

Penyederhanaan CFG dapat di lakukan dengan 3 cara :

1. Penghilangan produksi useless
2. Penghilangan produksi unit
3. Penghilangan produksi Є

Context Free Grammar (CFG)

Context Free Grammar (CFG)/ Bahasa Bebas Konteks adalah sebuah tata bahasa dimana tidak terdapat pembatasan pada hasil produksinya, Contoh Pada aturan produksi :

α → β

batasannya hanyalah ruas kiri (α) adalah sebuah simbol variabel. Sedangkan contoh aturan produksi yang termasuk CFG adalah seperti di bawah :

• B → CDeFg
• D → BcDe

Context Free Grammar ( CFG ) adalah tata bahasa yang mempunyai tujuan sama seperti halnya tata bahasa regular yaitu merupakan suatu cara untuk menunjukkan bagaimana menghasilkan suatu untai-untai dalam sebuah bahasa.

Teori bahasa dan Otomata (TBO) – NFA dengan ε-Move

Def 1.  ε-move adalah suatu transisi antara 2 status tanpa adanya input. Contoh gambar : transisi antara status q₁ ke q₃

NFA dengan e-Move

Def 2.  ε-closure adalah himpunan state yang dapat dicapai dari suatu state tanpa adanya input. Contoh gambar :

• ε-closure(q₀) = [q₀,q₁,q₃]
• ε-closure(q₁) = [q₁,q₃]
• ε-closure(q₃) = [q₃]

Teori Bahasa dan Otomata (TBO) – Finite State automata

Materi Teori Bahasa dan Otomata (TBO) ini membahas tentang pengertian FSA, contoh aplikasi, pendefinisian FSA dalam DFA dan NDFA, dan mereduksi DFA.

finite state automata

Finite State Automata (FSA) adalah model matematika yang dapat menerima input dan mengeluarkan output. FSA Memiliki state yang berhingga banyaknya dan dapat berpindah dari satu state ke state lainnya berdasar input dan fungsi transisi. FSA  Tidak memiliki tempat penyimpanan/memory, hanya bisa mengingat state terkini. Mekanisme kerja dapat diaplikasikan FSA pada : elevator, text editor, analisa leksikal, pencek parity.

Download Materi selengkapnya(pdf): Disini

Materi yang berhubungan:

Teori Bahasa Otomata (TBO) – Ekuivalensi NFA – DFA

EKUIVALENSI NFA-DFA Ada apa dengan NFA ? konsep yang sulit diimplemen-tasikan. Komputer sepenuhnya deterministic. Kenapa dipelajari ? Lebih dekat ke sistem nyata Contoh : permainan catur, banyak alternatif pada suatu posisi tertentu -> nondeterministic Algoritma : Buat semua state yang … Continue reading →

Teori Bahasa Otomata (TBO) – Kisi-kisi UTS 2011

Teori Bahasa Otomata (TBO) - Kisi UTS 2011

1. Diketahui grammar G(V, V, S, P) dimana :
V = {a, b}
V = {S, A, B}
S ε Vn
P = {S –> aA;  A–> aB| b; B–> bS;  }

• G termasuk grammar tipe berapa? Berikan alasannya.
• Buatlah 5 kalimat dengan panjang berbeda yang dapat diturunkan dari grammar G.
• Tentukan bahasa dari grammar G ( L(G)).

 

Teori Bahasa Otomata (TBO) – Ekuivalensi NFA – DFA

EKUIVALENSI NFA-DFA
Ada apa dengan NFA ? konsep yang sulit diimplemen-tasikan. Komputer sepenuhnya deterministic.
Kenapa dipelajari ? Lebih dekat ke sistem nyata
Contoh : permainan catur, banyak alternatif pada suatu posisi tertentu -> nondeterministic

Algoritma :

1. Buat semua state yang merupakan subset dari state semula. jumlah state menjadi 2^Q
2. Telusuri transisi state–state yang baru terbentuk, dari diagram transisi.
3. Tentukan state awal : {q₀}
4. Tentukan state akhir adalah state yang elemennya mengandung state akhir.
5. Reduksi state yang tak tercapai oleh state awal.
6. Rename nama-nama state yang tersisa.

Download Materi Selengkapnya: Disini

Teori Bahasa Otomata (TBO) – Nilai Quis 1 Kelas SI-TI-4G Amikom

`Adam Malik——80
Adhe Yanuar——90
Aditya Novaruna W——90
Afif Nourzamany——100
Ahmad Sa’di——98
Ahmad Saifudin——100
Ahmad Susanto——95
Aida Putri Purnamasari——85
Andang Eko Nugroho——80
Andrian Dwi Yuli K——80
Angga Fitra Kurniawan——98
Anggita——98
Anung Prasetyo——85
Arif Riyanto——95
Asmawati Septiana——100

Teori Bahasa Otomata (TBO) – Nilai Quis 1 Kelas SI-TI-4F Amikom

Achmad Mustagfiri-90
Achmaduri Al Achmad M-80
Adhitya Aziz NS-100
Agusdi Syafrizal-85
Ahmad Arifin Aziz-95
Ahmad Zahid-90
Anang Weby Kurniawan-100
Andi Hermawan-90
Andi Kurniawan-100
Andriana Darmawan-100
Ardhianta BN-100
Arief Budi Kusuma-100
Arief Munandar-98
Arman Annas Putra-90