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

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

Baca lebih lanjut

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 Є

Baca lebih lanjut

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.

Baca lebih lanjut

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

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 q1 ke q3

NFA dengan e-Move

NFA dengan e-Move

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

  • ε-closure(q0) = [q0,q1,q3]
  • ε-closure(q1) = [q1,q3]
  • ε-closure(q3) = [q3]

Baca lebih lanjut

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

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)).

  Baca lebih lanjut