Tài liệu Môn Lý Thuyết Automat&NNHT - 501038

Dành cho câu 1 đến câu 3: Cho các ngôn ngữ sau (chú ý n, m nguyên không âm):
L1 = {w ∈ {a, b, c}*: na(w) = nb(w) + nc(w)} L2 = {anbm: n > m} L3 = {anbm: n ≠ m}
1. Văn phạm nào sinh ra L1
(A). S → aSX | XSa | λ
X → b | c
(B). S → aSXS | XSaS | λ
X → b | c
(C). S → aSX | XSa | SS | λ
X → b | c
(D). Cả B, C đúng (E).Tất cả đều sai.
2. Văn phạm nào sinh ra L2
(A). S → aSb | a (B). S → aSb | aS | a (C). S → aSb | aS | λ (D). S → aSb | SS | a (E). Tất cả đều sai.
3. Văn phạm nào sinh ra L3
(A). S → A | B
A → aA | aX
B → Bb | Xb
X → aXb | λ
(B). S → A | B
A → aAb | a
B → aAb | b
(C). S → aS | Sb | a | b
(D). Cả A, B, C đúng (E). Tất cả đều sai.
Dành cho câu 4 đến câu 8 7: Cho văn phạm G sau: E → EE* | EE+ | a | b. G có tập kí hiệu kết thúc là {a, b, *, +}