Grammar Dan Bahasa || Nur Anisah Fadhilah - 202131020

Institut Teknologi PLN Jakarta

Dosen : DINE TIARA KUSUMA, S.T., M.Kom

GRAMMAR DAN BAHASA

Grammar

Grammar adalah sebagai kumpulan dari himpunan-himpunan variabel, simbol-simbol terminal, simbol awal, yang dibatasi oleh aturan-aturan produksi. Aturan Produksi merupakan pusat grammar yang menspesifikasikan bagaimana suatu grammar melakukan transformasi suatu string atau karakter ke bentuk lainnya.

Semua aturan produksi dinyatakan dalam bentuk "ɑ => β" (bisa dibaca ɑ menghasilkan β, atau dibaca ɑ menurunkan β). ɑ merupakan simbol-simbol pada ruas kiri aturan produksi, sedangkan β merupakan simbol-simbol ruas kanan aturan produksi.

• Simbol-simbol tersebut dapat berupa Simbol Terminal (Vt) atau Simbol Non-Terminal/Variabel (Vn).
• Simbol Vn adalah simbol yang masih dapat diturunkan, biasanya identik dengan huruf besar/kapital 'A', 'B', 'C'.
• Simbol Vt adalah simbol yang sudah tidak dapat diturunkan, biasanya identik dengan huruf kecil 'a', 'b', 'c'.

Dengan menerapkan aturan produksi, suatu grammar bisa menghasilkan sejumlah string.

Contoh aturan produksi :

1. E => T | T + E | T * E
2. T => a

Dari aturan produksi diatas, menghasilkan suatu variabel a atau variabel ekspresi a+a atau a*a.

1. E => T

    T => a

2. E => T + E

    E => a + T

    E => a + a

3. E => T * E

    E => a * T

    E => a * a

Grammar (G) di definisikan sebagai pasangan 4 tupple : Vt, Vn, S, dan Q. Dapat dituliskan sebagai G(Vt, Vn, S, dan Q) dimana :

Vt : Himpunan simbol-simbol terminal (himpunan token-token atau alfabet).

Vn : Himpunan simbol-simbol non terminal.

S : Simbol awal (simbol start).

Q : Himpunan produksi.

Derivarasi Kalimat Dan Penentuan Bahasa

1. Tentukan bahasa dari masing-masing grammar berikut : 

    G1 dengan Q1 = {1. S => aAa,    2. A => aAa,    3. A => b}

    Jawab :  

    - Derivasi Kalimat Terpendek : 

       S => aAa     (1)

       S => aba      (3)

    - Derivasi Kalimat Umum : 

       S => aAa           (1)

       S => aaAaa       (3)

       S => aaaAaaa    (1)

       S => aaabaaa     (3)

    - Dari pola kedua kalimat disimpulkan : 

       L₁(G₁) = {aⁿbaⁿ | n >= 1}

 2. Tentukan bahasa dari masing-masing grammar berikut : 

    G2 dengan Q2 = {1. S => aS,    2. S => aB,    3. B => bc,    4. C => aC,    5. C => a}

    Jawab :  

    - Derivasi Kalimat Terpendek 1 :

       S => aS           (1)

       S => aaB         (2)

       S => aabC       (3)

       S => aaba        (5)

    - Derivasi Kalimat Terpendek 1 :

       S => aS           (1)

       S => aaB         (2)

       S => aabC       (3)

       S => aabaC     (4)

       S => aabaa      (5)

    - Derivasi Kalimat Umum : 

       S => aS               (1)

       S => aaS             (1)

       S => aaaS           (1)

       S => aaaaB         (2)

       S => aaaabC       (3)

       S => aaaabaC     (4)

       S => aaaabaaC   (4)

       S => aaaabaaa    (5)

    - Dari pola kedua kalimat disimpulkan : 

      L₂(G₂) = {aⁿba^m | n > 1, m >= 1}

 

Teori Bahasa Dan Otomata serta Hirarki Chomsky || Nur Anisah Fadhilah - 202131020

 

Institut Teknologi PLN Jakarta

Dosen : DINE TIARA KUSUMA, S.T., M.Kom

PENJELASAN TEORI BAHASA DAN OTOMATA SERTA HIRARKI CHOMSKY

Bahasa 

Bahasa disebut sebagai rangkaian simbol - simbol yang mempunya makna.

Otomata 

• Otomata merupakan suatu sistem yang terdiri atas sejumlah 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

Bahasa & Otomata 

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

Penjelasan : 

• Sebuah string input diterima bila mencapai state akhir (final state) yang ada pada contoh disamping digambarkan dengan lingkaran ganda.
• Mesin ini memiliki 6 state yaitu q0, q1, q2, q3, q4, q5. State awal yaitu q0. q3 dan q4 adalah state akhir, sedangkan simbol input nya yaitu a,  d, u. 

1. ada : diterima
2. adu : diterima
3. add : ditolak

Konsep Teori Bahasa & Otomata 

• Teori Bahasa adalah konsep-konsep pada "string alpabet - dalam penyambungan karakter-karakter alpabet untuk membentuk suatu makna (bahasa).
• Alpabet adalah himpunan simbol (karakter) tidak kosong dan berhingga Alpabet dilambangkan dengan Zigma.
• String adalah deretan simbol dari alphabet dimana perulangan simbol diijinkan.

Contoh : 

V = (a, b, c, d)

String pada alpabet V antara lain -> "a", "abcd", "bbba".

• Panjang String adalah jumlah simbol di dalam string bukan pada alpabet dan pengulangan. Kemunculan simbol dihitung.

Contoh :

|c| = 0

|a| = 1

|aa| = 2

|aaa| = 3

|aaab| = 4

• Empty String (null string) adalah string yang tidak mengandung simbol apapun. Lambang nya ɛ atau 𝛌.

• Regular Expression adalah cara untuk mengekspresikan bahasa dengan hanya menggunakan operasi :

- Concatenation (Penyambungan)

  Contoh : 'a' o 'b' = 'ab'

- Superscript (Perkalian)

  Contoh : V o V = VV = V2

- Kleene Closure (String Tanpa Simbol)

  Contoh :

  ɛ mempunyai sifat identitas, yaitu :

  ɛ o x = x

  x o ɛ = x

- Positif Closure (Tidak Ada String Kosong Didalamnya)

  Vt = V1 U V2 U V3 U ......

Hirarki Chomsky

Secara umum tata bahasa dirumuskan sebagai berikut :

ɑ => β, yang berarti ɑ menghasilkan β, atau ɑ menurunkan β.

• 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 Aturan Produksi

- T => ɑ

dibaca "T menghasilkan a"

- E => T | T + E

dibaca "E menghasilkan T" atau "E menghasilkan T dan E"

- Simbol | menyatakan 'atau', digunakan untuk mempersingkat penulisan aturan produksi yang mempunyai ruas kiri yang sama.

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

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

• Tipe 2 / Bebas Konteks / Context Free

Aturan :

- Simbol pada sebelah kiri harus berupa sebuah simbol variabel

Contoh :

B => CDeFG (diterima)

D => BcDe (diterima)

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

• Tipe 3 / Reguler Aturan

Aturan :

- Simbol pada sebelah kiri harus berupa sebuah simbol variabel

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

Peta Karnaught dan Maxterm & Mintem

                                                                                            Institut Teknologi PLN Jakarta

Dosen : Max Teja Ajie Cipta Widiyanto, S.Kom., M.Kom

PETA KARNAUNGHT DAN MAXTERM & MINTEM

TUGAS KELOMPOK, yang beranggotakan : -Nur Anisah Fadhilah (202131020)

  -Siti Nurul Maghfirah (202131125)

Peta Karnaugh adalah sebuah metode untuk:

1. Menyederhanakan sebuah fungsi persamaan logika. Menyederhanakan fungsi persamaan logika  sebenarnya bisa dilakukan dengan menggunakan aturan-aturan baku seperti:

• Distributif. Misalnya (p ∧ q) ∨ (p ∧ r) ≡ p ∧ (q ∨ r)  atau (p ∨ q) ∧ (p ∨ r) ≡ p ∨ (q ∧ r).

• De Morgan seperti ~p ∨ ~q ≡ ~(p ∧ q) atau ~p ∧ ~q

• Hukum penyerapan  seperti p ∧ (p ∨ q) ≡ p atau p ∨ (p ∧ q) ≡ p

2. Mencari fungsi persamaan logika dari sebuah tabel kebenaran. Terkadang, kita memiliki sebuah tabel  kebenaran (yang diperoleh dari pengumpulan kasus atau kejadian) tetapi belum memiliki persamaan logikanya sehingga sulit membuat untai rangkaian logikanya.

Permasalahan-permasalahan diatas dapat diselesaikan dengan peta karnaugh.

Peta Karnaugh di-"ilustrasikan" seperti matrik 2 dimensi (terdiri atas baris dan kolom) dimana komponen baris dan kolom adalah masukan (input) dari sistem. Input dari masukan inilah yang kemudian disebut variabel K-Map nya. Sehingga ada sebutan K-Map 2 Peubah, K-Map 3 Peubah, 4 peubah dst.

K-Map efektif digunakan hanya sampai 6 peubah saja. Untuk peubah lebih dari 6, tidak lagi di-rekomendasikan menggunakan K-Map karena komputasinya sangat tinggi sehingga disarankan menggunakan program komputer khusus. Tutorial kali ini, saya akan membahas K-Map hingga 4 Variabel.

Menggambar peta karnagh

Peta Karnaugh 2 Peubah:

Ilustrasi berikut adalah peta karnaugh 2 peubah (A dan B).

Kelompok Baris adalah masukan A dan Kelompok Kolom adalah masukan B. Tidak ada yang spesial dari aturan K-Map 2 Variabel. Anda bisa menulisnya 0 kemudian 1 (sesuai contoh) atau 1 kemudian 0.

Sekarang kita lihat tabel kebenaran dari fungsi yang akan kita buat. Asumsikan, kita tidak memiliki fungsi persamaan dari tabel kebenaran berikut dan kita akan membuatnya.

Setiap cell dari matrik (bagian tengah) akan kita isi dengan hasil atau result dari tabel kebenaran. Sebagai contoh:

Peta Karnaugh 3 Peubah:

Sedikit berbeda dengan peta karnaugh 2 peubah, K-Map 3 peubah menggunakan 2 peubah di satu rusuk dan 1 peubah di rusuk yang lain. Anda bisa membuat K-Map dengan 2 peubah di rusuk tegak, dan 1 peubah di rusuk mendatar atau sebaliknya. Perhatikan gambar:

Yang perlu diperhatikan di sini adalah penyusunan kombinasi masukan 2 peubah harus mengikuti kaidah "perubahan di satu tempat". Artinya transisi dari "0" ke "1" hanya di satu tempat saja. Sebagai contoh, kombinasi masukan dari "01" menjadi "11". Transisi yang terjadi pada kombinasi ini hanya pada masukan A (dari 0 menjadi 1) sedangkan masukan B tetap (1 tetap 1). Jadi anda tidak boleh menulis "01" kemudian "10" (seperti yang biasa anda lakukan di tabel kebenaran). Mengapa? karena jika susunan-nya "01" kemudian "10", berarti perubahan terjadi di 2 masukan, A berubah dari "0" menjadi "1" dan masukan B berubah dari "1" menjadi "0".

Seperti pada K-Map 2 peubah, isi Cell dari K-Map 3 peubah juga berisi result (hasil) dari tabel kebenaran. Sebagai contoh

Anda boleh menggunakan K-Map yang atas atau yang bawah.

Peta Karnaugh 4 Peubah:

Untuk K-Map 4 peubah, anda dapat memasukkan 2 peubah di rusuk tegak dan 2 peubah di rusuk mendatar. Perhatikan gambar:

Daerah Minterm

Nah sekarang kita sudah bisa menggambar peta Karnaugh atau K-Map dengan 2, 3 dan 4 peubah. Proses berikutnya adalah menentukan daerah minterm. Daerah minterm adalah sebuah daerah di dalam K-Map yang berisi nilai 1 yang "bertetangga" (akan dijelaskan dalam contoh). Keanggotaan sebuah daerah minterm bisa berisi 2^n dimana n bernilai 0, 1, 2, 3, ... dst. Sehingga keanggotaan wilayah minterm bisa 1, 2, 4, 8, 16, dst.

Melukiskan daerah minterm, bisa secara vertikal (atas bawah) atau horisontal (kiri dan kanan) tetapi tidak bisa secara diagonal.

Contoh daerah minterm untuk K-Map 2 peubah adalah sebagai berikut:

Keterangan:

(A): Karena nilai "1" hanya ada satu, maka daerah mintermnya juga hanya 1.

(B): Nilai "1" ada di dua tempat (cell) tetapi mereka bertetangga secara diagonal, maka angka-angka "1" tersebut tidak bisa menjadi satu wilayah minterm.

(C): Terdapat 2 wilayah minterm dengan masing-masing memiliki 2 anggota angka "1".

(D): Mirip dengan kasus point (B).

Sedikit berbeda untuk K-Map dengan dimensi yang lebih besar(di atas dimensi 2x2), K-Map "dipandang sebagai sebuah bidang yang "bulat" seperti globe. Artinya daerah minterm bisa saja "menyatukan" angka 1 yang di sisi atas dan bawah atau kiri dan kanan secara berputar. Lihat contoh di bawah ini:

Ingat: Tidak bisa diagonal saja.

Membangun persamaan dari daerah minterm di K-Map

Setelah daerah minterm sudah kita tandai, proses berikutnya adalah menentukan persamaan dari daerah minterm tersebut. Kita bisa menggunakan asas "konsistensi" untuk memudahkan membangun persamaan daerah minterm tersebut. Konsistensi yang saya maksud adalah nilai masukan yang TIDAK BERUBAH di setiap sel daerah minterm. Sebagai contoh untuk daerah minterm yang hanya berisi satu anggota seperti pada gambar berikut:

Karena kita tidak bisa membuat daerah minterm secara diagonal maka K-Map di atas memiliki 2 daerah minterm. Untuk daerah mintem yang berisi satu anggota saja, membuat persamaannya cukup mudah. Cukup lihat masukan untuk setiap daerah minterm tersebut.

Daerah minterm 1: masukan dari sisi baris adalah A'B dan dari sisi kolom adalah C'. Nilai akses (') di sini mengacu pada nilai 0 pada masukan A dan C (sedangkan karena nilai B bernilai "1" maka tidak diberi aksen atau NOT).

Daerah minterm 2: masukan dari sisi baris adalah AB dan dari sisi kolom adalah C (semua nilai masukan "1" maka tidak ada aksen)

Sehingga fungsi persamaan dari K-Map tersebut adalah: A'BC + ABC.

Pembuktian dengan tabel kebenaran:

Untuk daerah minterm yang berisi lebih dari satu, asas konsistensi bisa kita gunakan. Perhatikan contoh:

Pada contoh di atas, daerah mintem yang terbentuk memiliki empat anggota dimana masukannya adalah:

• Sisi Baris (AB): 01 dan 11
• Sisi Kolom (CD): 01 dan 11

Nilai yang konsisten di sisi baris adalah B. (A tidak konsisten karena ada A yang bernilai "1" dan ada A yang bernilai "0". Sedangkan nilai yang konsisten di sisi kolom adalah D. (nilai C tidak konsisten).

Sehingga persamaan untuk K-Map di atas adalah BD. Lihat pada tabel kebenaran berikut:

Contoh lain:

Daerah minterm 1 (yang berwarna biru): Masukan yang konsisten di sisi baris (masukan AB) adalah B dan masukan yang konsisten di sisi kolom adalah C sehingga rumus fungsinya adalah BC

Daerah minterm 2 (yang berwarna merah): Masukan yang konsisten di sisi baris (masukan AB) tidak ada (semuanya (baik A dan B) tidak ada yang konsisten) sedangkan masukan yang konsisten di sisi kolom adalah CD'.

Sehingga persamaan fungsi dari K-Map di atas adalah F = BC + CD'. Perhatikan tabel kebenaran berikut:

Sekian dan Terima Kasih