Otomat_tink27-dapan

ĐÁP ÁN THI KẾT THÚC HỌC PHẦN − LỚP TIN K27 Môn thi: NGÔN NGỮ HÌNH THỨC VÀ ÔTÔMAT Câu I: (1 điểm) L(G) = { xaa | x ∈ {a, b}* } Câu II: (2 điểm) a) (1 đ) G1=<{0, 1}, {S1, A, B}, S1, {S1→0A, A→1A, A→0B, B→1B, A→0, B→1}> b) (0,5 đ) G2=<{0, 1}, {S2, C}, S2, {S2→C1, C→0C0, C→1}> c) (0,5 đ) G=<{0, 1}, {S1, A, B, S2, C, S}, S, P}, trong đó: P={S→S1, S→S2, S1→0A, A→1A, A→0B, B→1B, A→0, B→1,S2→C1, C→0C0,C→1}

Câu III: (0,5 điểm) Tìm một phản ví dụ (chẳng hạn: (0 + 1)* ≠ 0* + 1*) Câu IV: (1,5 điểm) a) (0,5 đ)

a

a

q0

q1

b

b

q2

b a

q3 b

b) (1 đ) aa*bb* + b(a+b)*

Câu V: (1,5 điểm) a) (0,5 đ) abc(abc)*(cbac)* b) (1 đ) q0

a

b

q1

a

q3

q2

c

c

c

q4

q6

b

q5

a

Câu VI: (1,5 điểm) ω = a∗b+c∗a∗b+c a) (1 đ) S ∗

A S

+

∗

A

S

A

a

A S

c

A

b

+

∗

S

A

a

c

b

b) (0,5 đ) G là nhập nhằng vì ω còn là kết quả của cây sau: S +

S ∗

A a

S

A

A

b

c

∗

A

A S

+

S

∗

A

c

b

a

Câu VII: (2 điểm): a) (1 đ) s0



s1



<1/1, R>

b) (1 đ) <ε, s0, B13B14>

s2



<1/1, R>

s3

<1/B, L>

s4

<1/B, L>

s5

<1/1, L>

<ε, s1, 13B14> <1, s1, 12B14> <11, s1, 1B14> <111, s1, B14> <14, s2, 14> <15, s2, 13> <16, s2, 12> <17, s2, 1> <18, s2, B> <17, s3, 1> <16, s4, 1> <15, s5, 1> <14, s5, 12> <13, s5, 13> <12, s5, 14> <1, s5, 15> <ε, s5, 16> <ε, s5, B16>.