UTS Teori dan Bahasa Automata
SOAL UJIAN TENGAH/AKHIR SEMESTER
Mata Kuliah : Teori dan Bahasa Automata Tanggal : 6 Juni 2020
Fakultas : Teknologi Industri Waktu : 90 Menit
Jenjang / Jurusan : S1 / Teknik Informatika Dosen : Erwin Suhandono
Tingkat / Kelas : III/ 3IA05 dan 3IA08 Sifat Ujian : Tutup Buku
Semester/Tahun : ATA – 2019 /2020 Juml. Soal : 5 soal essay
Petunjuk mengerjakan soal :
1. Jawaban ujian diketik dan disimpan dalam form doc, docx (Ms. Word) atau PDF ( disertakan dalam paket soal ini ).
2. Format nama file MS.Word atau PDF harus menggunakan format seperti dibawah ini :
kelas_namamatakuliah_NamaMahasiswa_NIM_UTSTBA2020
3. Kirim kealamat email suhandonodepok@gmail.com
Soal :
1. Buatlah deterministik finite automata yang equivalen dengan non deterministik finite automata berikut :
Q = {p, q, r, s}
∑ = {a, b}
S = p
F = {q, s}
| a | B |
p | q, s | Q |
q | r | q,r |
r | s | P |
s | - | P |
a. Dari gambar diatas telusurilah apakah kalimat berikut diterima abbba,aaaabbbb,abababbaa berikut dengan caranya ?
b. Buatlah 4 kalimat yang tidak diterima dan yang diterima dengan berikut caranya ?
2. Untuk tata bahasa konteks berikut : S → FE | h , F → Fg | hE , E → g | ih | gh Berikanlah pemetaan untuk memperoleh untaian pada parsing di bawah ini termasuk gagal atau tidak?
3. Ujilah decimal 88 apakah diterima oleh mesin DFA pada kalimat dibawah berikut ?
Q = {a,b,c,d,e}
Σ = {0,1}
S = {b}
F = {a,b,c}
Fungsi transisi δ :
δ | 0 | 1 |
a | e | a |
b | a | c |
c | e | c |
d | b | a |
e | d | d |
4. Jelaskan metode parsing ?
5. Jelaskan bagaimana sebuah kalimat dapat diterima oleh AHD dan AHN ?
Q = {p, q, r, s}
∑ = {a, b}
S = p
F = {q, s}
| a | B |
p | q, s | Q |
q | r | q,r |
r | s | P |
s | - | P |
Semua
simbol variabel berhasil di turunkan menjadi simbol terminal dan tidak
ada simbol variabel yang belum tergantikan, maka pasing pada tata bahasa
konteks nomor 2 dikatakan berhasil. Perhatikan gambar diatas adalah
pembuktiannya.
3. Diketahui
Q = {a,b,c,d,e}
Σ = {0,1}
S = {b}
F = {a,b,c}
Fungsi transisi δ :
δ | 0 | 1 |
a | e | a |
b | a | c |
c | e | c |
d | b | a |
e | d | d |
8801 : 0001100 |…..(a,001100) dengan δ (b,0) = a
(b,0001100) |…..(e,01100) dengan δ (a,0) = e
(a,001100) |…..(d,1100) dengan δ (e,0) = d
(e,01100) |…..(a,100) dengan δ ( d,1) = a
(d,1100) |…..(a,00) dengan δ (a,1) = a
(a,100) |…..(e,0) dengan δ (a,0) = a
(e,0) |…..(d,
) dengan δ (e,0) = d <------DITOLAK
