UTS Teori Bahasa dan Otomata 2025

1. NFA dan subset construction

a. NFA adalah (Q, Σ, δ, q0, F) dengan Q berisi q0 sampai q4, alfabet a,b,c, dan final q0,q3,q4. Transisi yang tidak disebut menghasilkan himpunan kosong:

Keadaan	a	b	c
q0	q1,q2	∅	∅
q1	q1	q3,q4	q2,q3,q4
q2	q3,q4	∅	∅
q3	∅	∅	∅
q4	q3	∅	q4

b–c. DFA dimulai dari subset 0; subset diterima jika mengandung 0, 3, atau 4. Tabel berikut menuliskan q1 sebagai 1, dan set kosong sebagai ∅; tiap entri adalah union transisi NFA.

Subset	a	b	c	Final?
0	12	∅	∅	ya
12	134	34	234	tidak
134	13	34	234	ya
34	3	∅	4	ya
234	34	∅	4	ya
13	1	34	234	ya
3	∅	∅	∅	ya
4	3	∅	4	ya
1	1	34	234	tidak
∅	∅	∅	∅	tidak

d. String aaacacca diterima: 0 → 12 → 134 → 13 → 234 → 34 → 4 → 4 → 3, dan subset terakhir mengandung q3 final.

NFA: jejak aaacacca

1 / 4

Mulai

Mulai pada q0.

Subset0

↺SebelumnyaPutarBerikutnyaLangkah

2. DFA minimal, ekspresi, dan grammar

a. Gabungkan q1 dengan q4, q2 dengan q5, dan q3 dengan q6 karena masing-masing pasangan mempunyai status final dan perilaku lanjutan sama. Misal A = q1/q4, B = q2/q5, C = q3/q6, D = q7, dan I = q0. Alfabet a,b; awal I; final A,B,C:

State	a	b	Final
I	A	A	tidak
A	B	C	ya
B	D	D	ya
C	D	C	ya
D	D	D	tidak

b. Ekspresi regulernya (a+b)(a+b*): simbol pertama bebas, lalu boleh sebuah a atau sejumlah b termasuk nol.

c. Grammar linear kanan: I → aA | bA, A → λ | aB | bC, B → λ | aD | bD, C → λ | aD | bC, D → aD | bD. D tidak menghasilkan kata terminal sehingga dapat dihilangkan bersama produksi menuju D jika grammar dipersingkat.

3. Bahasa dari ekspresi

Dengan definisi induktif, L(a+b) = {a,b} dan L(b*) = {λ,b,bb,...}. Maka L((a+b)(a+b*)) berisi semua string yang simbol pertamanya a atau b, diikuti salah satu dari sebuah a atau nol/lebih b. Contoh a, b, aa, ba, ab, bbb; aba tidak termasuk. Kurung kurawal di sini menyatakan himpunan, bukan urutan output.

4. Grammar untuk aⁿbᵐ dengan n ≥ 3 dan m ≥ 2

a. Linear kanan:

S → aA
A → aB
B → aC
C → aC | bD
D → bE
E → bE | λ

Tiga a dan dua b pertama wajib; loop C dan E menambah sisanya.

b. Linear kiri:

S → Sb | Ab
A → Bb
B → Ba | Ca
C → Da
D → a

Dari dalam ke luar grammar menghasilkan minimal tiga a, kemudian dua b; loop B dan S menambah masing-masing simbol.

c. Keduanya adalah G = (V, T, P, S), dengan T = {a,b} dan P masing-masing kumpulan aturan di atas. Untuk grammar kanan V adalah S,A,B,C,D,E; untuk grammar kiri V adalah S,A,B,C,D. Contoh minimal adalah aaabb, dan tidak satu pun dapat membangkitkan b sebelum a atau kurang dari batasnya.