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

 

2. Diketahui sebuah NFA (Q, ∑, δ, S, F). dimana :

Q = {q0, q1, q2, q3}, ∑= {0, 1},  S = q0 , F = { q0, q1}

δ diberikan dalam tabel transisi berikut :

d 0 1
q0 { q0, q1 , q2} {}
q1 {q2} {q3}

q2

{q3}

{q1}

q3

{q3}

{q3}

  1. Gambarlah diagram transisi (graf) dari NFA di atas.
  1. Buatlah 3 kalimat/string dengan panjang berbeda yang diterima oleh NFA di atas dan 3 kalimat/string dengan panjang berbeda yang ditolak oleh NFA di atas.

3.       Diketahui sebuah NFA (Q, ∑, δ, S, F). dimana :

Q = {q0, q1, q2}, ∑= {0, 1},  S = q0 , F = { q2 }

δ diberikan dalam tabel transisi berikut :

d 0 1
q0 { q0 } { q0 , q1}
q1

{q2}

{}
q2 {} {}

Buatlah Deterministic Finite Automata (DFA) yang ekuivalen dengan NFA di atas dan kemudian gambarlah diagram transisi dari DFA saudara.

4.   Diberikan dua string : x = 3 huruf nama belakang anda, dan y = 3 angka nomahasiswa

  • semua Prefix(x)
  • semua ProperPrefix(y)
  • semua Postfix(x)
  • semua ProperPostfix(y)
  • Head(x)
  • Tail(y)
  • semua Substring(x)
  • semua Substring(y)
  • semua Subsequence(x)
  • Concate(yx)
  • Alternate(xy) = x½y
  • Head(x)Tail(y)
  • Concate(Tail(y)xy)

Download pdf: Disini

Posting yang terkait:

Pendahuluan

Pada materi Teori Bahasa Otomata (TBO) ini dibahas tentang Pengertian TBO, Model Komputasi TBO, Peranan TBO dalam Ilmu Komputer dan Contoh Penerapan TBO. Komputer mengikuti sejumlah prosedur sistematis, atau algoritme, yang dapat diaplikasikan untuk serangkaian input (string) yang menyatakan integer … Continue reading →

String dan Operasi String

Pada materi teori bahasa dan otomata dibahas tentang: Beberapa Istilah Pengertian string Operasi string Prefik ProperPrefix Postfix (atau Sufix) ProperPostfix (atau PoperSufix) Head Tail Substring ProperSubstring Subsequence ProperSubsequence Concatenation Alternation Kleene Closure Positive Closure Sifat Operasi String Latihan Operasi String … Continue reading →

Konsep Grammar dan Bahasa

Teori Bahasa dan Otomata (TBO) kali ini membahas tentang Konsep Grammar dan Bahasa, meliputi bahasa: Konsep dasar, Aturan Produksi, Grammar dan Klasifikasi Chomsky. Contoh Analisa Penentuan Type Grammar, Derivasi Kalimat dan Penentuan Bahasa, Menentukan Grammar Sebuah Bahasa dan Latihan tentang … Continue reading →

Iklan

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s