Teori bahasa dan otomata

Sederhanakan dengan menghilangkan Unit

S → Sb

S → C dd I ef

C→ ef

D→ dd

Hasil penyederhanaanya adalah:

• S → Sb

  S:→ dd I ef

• S → bb

  S:→ dd I ef

• S → Sb

  S:→ dd I ee

• S → Sb

  S:→ bb I ef

• S → Sb

  S:→ ee I ef

S→ AB | a

A → a

Aturan S→ AB tidak berarti karena B

• tidak memiliki penurunan

• memiliki penurunan

• tidak bisa diremehkan

• tidak memiliki induk

• tidak seimbang

Dalam Penerapan Ekspresi Reguler: Sebuah bahasa dinyatakan regular jika:.......

• terdapat finite state automata (FSA) yang dapat menerimanya

• tidak terdapat finite state automata (FSA) yang dapat menerimanya

• sebagian terdapat finite state automata (FSA) yang dapat menerimanya

• terdapat finite state automata (FSA) yang tidak dapat menerimanya

• finite state automata (FSA) yang dapat menerimanya dapat digunakan secara umum

Prinsip penyederhanaan adalah: Prinsipnya setiap kali melakukan penyederhanan kita periksa lagi aturan produksi yang tersisa, apakah semua produksi yang useless sudah.........

• dihilangkan.

• diturunkan.

• diproses.

• dikembalikan.

• dimutasi.

Untuk bentuk produksi sebagai berikut:

S → bcAd

A → bd | ε

Pada kasus diatas A nullable, tapi A → ε

bukan satu2nya produksi dari A, maka hasil

penyederhanaan menjadi:

• S → bcAd | bcd

  A → bd

• S → bcAd | bcd

• A → bd

• A → bd | ε

• S → bcAd | bcd

  A → bd | ε

Dalam kasus Penghilangan Produksi Useless :

Karena tidak ada yg redundan dan semua aturan produksinya sudah sederhana, maka hasil dari penghilangan produksi useless =

• hasil dari penghilangan produksi ε

• hasil dari penambahan produksi ε

• hasil dari pengurangan produksi ε

• hasil dari manipulasi produksi ε

• hasil dari pengolahan produksi ε

Manakah yang merupakan Urutan prioritas operator tertinggi dalam ekspresi regular?

• Operator star (*)

• Operator dot (concatenation)(.)

  Concatenation bersifat asosiatif sehingga 012 dapat dikelompokkan (01)2.

• Operator (+) atau (υ)/ (union) yang bersifat asosiatif.

  Contoh, ekspresi 01*+1 dikelompokkan menjadi (0(1*))+1.

• Operator pengurangan (-)

• Operator Modulue (%)

Lakukan penghilangan aturan produksi unit, useless, dan ε dari tata bahasa bebas konteks berikut :

S → a | aA | B | C

A → aB | ε

B → Aa

C → cCD

D → ddd

Penghilangan Produksi ε :

A → ε dihilangkan, shg :

A → aB

B → Aa | a

S → a | aA | B | C

Penyederhanaannya Menjadi :

Penghilangan Produksi Useless :

1.C tidak memiliki penurunan, shg C → cCD dihilangkan

2.S → cCD dihilangkan

3.Konsekuensi no 2, D → ddd dihilangkan

Sehingga menjadi :

• S → a | aA | Aa

  A → aB

  B → Aa | a

• S → a | aA | B | C

  A → aB

  B → Aa

  C → cCD

  D → ddd

• S → a | aA | B | C

  A → aB

  B → Aa | a

  C → c

  D → dddS → a | aA | B | C

  A → aB

  B → Aa | a

  C → cCD

  D → ddd

• S → a | aA | B | C

  A → aB

  B → Aa | a

• S → a | aA | B | C

  A → aB

S→ AB | a

A → a

Aturan S→ AB tidak berarti karena B

• tidak memiliki penurunan

• memiliki penurunan

• tidak bisa diremehkan

• tidak memiliki induk

• tidak seimbang

Aturan Produksi berikut:

nS → A

A → B

B → C

C → D

D → a | A

Memiliki kelemahan yaitu terlalu panjang jalannya padahal berujung pada S → a, D → A juga menyebabkan.....

• kerumitan.

• kemudahan

• kepanjangan

• nilai kosong

• nilai mutlak