Bài giảng Ngôn ngữ hình thức và ô tô mát - Chương 1: Ngôn ngữ hình thức và ô tô mát - Nguyễn Thị Minh Huyền

ng, tập các quy tắc cú pháp để tạo ra câu
Định nghĩa hình thức: Văn phạm là một bộ bốn
G = (Σ,V , σ,P), trong đó:
Σ là bảng chữ cái chính, còn gọi là tập kí hiệu kết thúc
V là bảng chữ cái phụ, còn gọi là tập kí hiệu không kết hay
tập biến, V ∩ Σ = ∅
σ ∈ V là tiên đề (biến khởi tạo)
P là tập các quy tắc sinh có dạng α→ β,→/∈ Σ ∪ V ,
α ∈ (Σ ∪ V )+, β ∈ (Σ ∪ V )∗
Ch1. NN&VP hình thức 18 / 30
Văn phạm hình thức
Định nghĩa văn phạm
Ý nghĩa: Mô tả một ngôn ngữ bằng cách liệt kê tập từ
vựng, tập các quy tắc cú pháp để tạo ra câu
Định nghĩa hình thức: Văn phạm là một bộ bốn
G = (Σ,V , σ,P), trong đó:
Σ là bảng chữ cái chính, còn gọi là tập kí hiệu kết thúc
V là bảng chữ cái phụ, còn gọi là tập kí hiệu không kết hay
tập biến, V ∩ Σ = ∅
σ ∈ V là tiên đề (biến khởi tạo)
P là tập các quy tắc sinh có dạng α→ β,→/∈ Σ ∪ V ,
α ∈ (Σ ∪ V )+, β ∈ (Σ ∪ V )∗
Ch1. NN&VP hình thức 18 / 30
Văn phạm hình thức
Định nghĩa văn phạm
Ý nghĩa: Mô tả một ngôn ngữ bằng cách liệt kê tập từ
vựng, tập các quy tắc cú pháp để tạo ra câu
Định nghĩa hình thức: Văn phạm là một bộ bốn
G = (Σ,V , σ,P), trong đó:
Σ là bảng chữ cái chính, còn gọi là tập kí hiệu kết thúc
V là bảng chữ cái phụ, còn gọi là tập kí hiệu không kết hay
tập biến, V ∩ Σ = ∅
σ ∈ V là tiên đề (biến khởi tạo)
P là tập các quy tắc sinh có dạng α→ β,→/∈ Σ ∪ V ,
α ∈ (Σ ∪ V )+, β ∈ (Σ ∪ V )∗
Ch1. NN&VP hình thức 18 / 30
Văn phạm hình thức
Định nghĩa văn phạm
Ý nghĩa: Mô tả một ngôn ngữ bằng cách liệt kê tập từ
vựng, tập các quy tắc cú pháp để tạo ra câu
Định nghĩa hình thức: Văn phạm là một bộ bốn
G = (Σ,V , σ,P), trong đó:
Σ là bảng chữ cái chính, còn gọi là tập kí hiệu kết thúc
V là bảng chữ cái phụ, còn gọi là tập kí hiệu không kết hay
tập biến, V ∩ Σ = ∅
σ ∈ V là tiên đề (biến khởi tạo)
P là tập các quy tắc sinh có dạng α→ β,→/∈ Σ ∪ V ,
α ∈ (Σ ∪ V )+, β ∈ (Σ ∪ V )∗
Ch1. NN&VP hình thức 18 / 30
Văn phạm hình thức
Ví dụ
G = (Σ,V, σ,P)
Σ = {a,am, I, student , teacher}
V = {S,NP,VP,N,Det ,V ,P}
σ = S
Tập quy tắc P:
1. S → NP VP
2. NP → Det N | P
3. VP → V NP
4. Det → a
5. P → I
6. V → am
7. N → student | teacher
Ch1. NN&VP hình thức 19 / 30
Văn phạm hình thức
Dẫn xuất
Quan hệ dẫn trực tiếp: α ∈ (Σ ∪ V )∗ được gọi là dẫn (trực
tiếp) ra β ∈ (Σ ∪ V )∗, kí hiệu α⇒ β, nếu tồn tại quy tắc
x → γ ∈ P sao cho α = uxv và β = uγv .
Quan hệ dẫn⇒∗ là bao đóng bắc cầu của quan hệ dẫn
trực tiếp⇒.
Dẫn xuất n bước: α0 ⇒ α1 ⇒ ...⇒ αn
Ch1. NN&VP hình thức 20 / 30
Văn phạm hình thức
Dẫn xuất
Quan hệ dẫn trực tiếp: α ∈ (Σ ∪ V )∗ được gọi là dẫn (trực
tiếp) ra β ∈ (Σ ∪ V )∗, kí hiệu α⇒ β, nếu tồn tại quy tắc
x → γ ∈ P sao cho α = uxv và β = uγv .
Quan hệ dẫn⇒∗ là bao đóng bắc cầu của quan hệ dẫn
trực tiếp⇒.
Dẫn xuất n bước: α0 ⇒ α1 ⇒ ...⇒ αn
Ch1. NN&VP hình thức 20 / 30
Văn phạm hình thức
Dẫn xuất
Quan hệ dẫn trực tiếp: α ∈ (Σ ∪ V )∗ được gọi là dẫn (trực
tiếp) ra β ∈ (Σ ∪ V )∗, kí hiệu α⇒ β, nếu tồn tại quy tắc
x → γ ∈ P sao cho α = uxv và β = uγv .
Quan hệ dẫn⇒∗ là bao đóng bắc cầu của quan hệ dẫn
trực tiếp⇒.
Dẫn xuất n bước: α0 ⇒ α1 ⇒ ...⇒ αn
Ch1. NN&VP hình thức 20 / 30
Văn phạm hình thức
Ngôn ngữ sinh bởi văn phạm
Cho văn phạm G = (Σ,V , σ,P). Ngôn ngữ L sinh bởi văn
phạm G là tập tất cả các từ trên bảng chữ cái Σ dẫn được
từ tiên đề σ: L(G) = {w ∈ Σ∗|σ ⇒∗ w}
Ví dụ: Ngôn ngữ sinh bởi văn phạm đã cho trong ví dụ ở
trên?
Hai văn phạm G1 và G2 gọi là tương đương nếu
L(G1) = L(G2).
Ch1. NN&VP hình thức 21 / 30
Văn phạm hình thức
Ngôn ngữ sinh bởi văn phạm
Cho văn phạm G = (Σ,V , σ,P). Ngôn ngữ L sinh bởi văn
phạm G là tập tất cả các từ trên bảng chữ cái Σ dẫn được
từ tiên đề σ: L(G) = {w ∈ Σ∗|σ ⇒∗ w}
Ví dụ: Ngôn ngữ sinh bởi văn phạm đã cho trong ví dụ ở
trên?
Hai văn phạm G1 và G2 gọi là tương đương nếu
L(G1) = L(G2).
Ch1. NN&VP hình thức 21 / 30
Văn phạm hình thức
Ngôn ngữ sinh bởi văn phạm
Cho văn phạm G = (Σ,V , σ,P). Ngôn ngữ L sinh bởi văn
phạm G là tập tất cả các từ trên bảng chữ cái Σ dẫn được
từ tiên đề σ: L(G) = {w ∈ Σ∗|σ ⇒∗ w}
Ví dụ: Ngôn ngữ sinh bởi văn phạm đã cho trong ví dụ ở
trên?
Hai văn phạm G1 và G2 gọi là tương đương nếu
L(G1) = L(G2).
Ch1. NN&VP hình thức 21 / 30
Văn phạm hình thức
Phân lớp văn phạm của Chomsky (1)
Các kiểu quy tắc
Quy tắc tổng quát: không có ràng buộc về vế trái cũng như
vế phải
Quy tắc cảm ngữ cảnh: có dạng αAβ → αγβ, A ∈ V ,
α, β ∈ (Σ ∪ V )∗, γ ∈ (Σ ∪ V )+
Định nghĩa khác: α→ β, |α| ≤ |β|
Quy tắc phi ngữ cảnh: có dạng A→ α, A ∈ V , α ∈ (Σ∪V )∗
Quy tắc tuyến tính: có dạng A→ x hoặc A→ xBy ,
A,B ∈ V , x , y ∈ Σ∗
Quy tắc tuyến tính trái (phải): có dạng A→ a hoặc A→ 
hoặc A→ Ba (A→ aB), A,B ∈ V , a ∈ Σ
Ch1. NN&VP hình thức 22 / 30
Văn phạm hình thức
Phân lớp văn phạm của Chomsky (1)
Các kiểu quy tắc
Quy tắc tổng quát: không có ràng buộc về vế trái cũng như
vế phải
Quy tắc cảm ngữ cảnh: có dạng αAβ → αγβ, A ∈ V ,
α, β ∈ (Σ ∪ V )∗, γ ∈ (Σ ∪ V )+
Định nghĩa khác: α→ β, |α| ≤ |β|
Quy tắc phi ngữ cảnh: có dạng A→ α, A ∈ V , α ∈ (Σ∪V )∗
Quy tắc tuyến tính: có dạng A→ x hoặc A→ xBy ,
A,B ∈ V , x , y ∈ Σ∗
Quy tắc tuyến tính trái (phải): có dạng A→ a hoặc A→ 
hoặc A→ Ba (A→ aB), A,B ∈ V , a ∈ Σ
Ch1. NN&VP hình thức 22 / 30
Văn phạm hình thức
Phân lớp văn phạm của Chomsky (1)
Các kiểu quy tắc
Quy tắc tổng quát: không có ràng buộc về vế trái cũng như
vế phải
Quy tắc cảm ngữ cảnh: có dạng αAβ → αγβ, A ∈ V ,
α, β ∈ (Σ ∪ V )∗, γ ∈ (Σ ∪ V )+
Định nghĩa khác: α→ β, |α| ≤ |β|
Quy tắc phi ngữ cảnh: có dạng A→ α, A ∈ V , α ∈ (Σ∪V )∗
Quy tắc tuyến tính: có dạng A→ x hoặc A→ xBy ,
A,B ∈ V , x , y ∈ Σ∗
Quy tắc tuyến tính trái (phải): có dạng A→ a hoặc A→ 
hoặc A→ Ba (A→ aB), A,B ∈ V , a ∈ Σ
Ch1. NN&VP hình thức 22 / 30
Văn phạm hình thức
Phân lớp văn phạm của Chomsky (1)
Các kiểu quy tắc
Quy tắc tổng quát: không có ràng buộc về vế trái cũng như
vế phải
Quy tắc cảm ngữ cảnh: có dạng αAβ → αγβ, A ∈ V ,
α, β ∈ (Σ ∪ V )∗, γ ∈ (Σ ∪ V )+
Định nghĩa khác: α→ β, |α| ≤ |β|
Quy tắc phi ngữ cảnh: có dạng A→ α, A ∈ V , α ∈ (Σ∪V )∗
Quy tắc tuyến tính: có dạng A→ x hoặc A→ xBy ,
A,B ∈ V , x , y ∈ Σ∗
Quy tắc tuyến tính trái (phải): có dạng A→ a hoặc A→ 
hoặc A→ Ba (A→ aB), A,B ∈ V , a ∈ Σ
Ch1. NN&VP hình thức 22 / 30
Văn phạm hình thức
Phân lớp văn phạm của Chomsky (1)
Các kiểu quy tắc
Quy tắc tổng quát: không có ràng buộc về vế trái cũng như
vế phải
Quy tắc cảm ngữ cảnh: có dạng αAβ → αγβ, A ∈ V ,
α, β ∈ (Σ ∪ V )∗, γ ∈ (Σ ∪ V )+
Định nghĩa khác: α→ β, |α| ≤ |β|
Quy tắc phi ngữ cảnh: có dạng A→ α, A ∈ V , α ∈ (Σ∪V )∗
Quy tắc tuyến tính: có dạng A→ x hoặc A→ xBy ,
A,B ∈ V , x , y ∈ Σ∗
Quy tắc tuyến tính trái (phải): có dạng A→ a hoặc A→ 
hoặc A→ Ba (A→ aB), A,B ∈ V , a ∈ Σ
Ch1. NN&VP hình thức 22 / 30
Văn phạm hình thức
Phân lớp văn phạm của Chomsky (2)
Các lớp văn phạm
Kiểu 3: Văn phạm chính quy - các quy tắc là quy tắc tuyến
tính phải⇒ sinh ngôn ngữ chính quy
Kiểu 2: Văn phạm phi ngữ cảnh - các quy tắc là quy tắc phi
ngữ cảnh⇒ sinh ngôn ngữ phi ngữ cảnh
Kiểu 1: Văn phạm cảm ngữ cảnh - các quy tắc là quy tắc
cảm ngữ cảnh⇒ sinh ngôn ngữ cảm ngữ cảnh
Kiểu 0: Văn phạm không hạn chế/tổng quát - các quy tắc là
quy tắc tổng quát⇒ sinh ngôn ngữ tổng quát
L0 ⊃ L1 ⊃ L2 ⊃ L3
Ch1. NN&VP hình thức 23 / 30
Văn phạm hình thức
Phân lớp văn phạm của Chomsky (2)
Các lớp văn phạm
Kiểu 3: Văn phạm chính quy - các quy tắc là quy tắc tuyến
tính phải⇒ sinh ngôn ngữ chính quy
Kiểu 2: Văn phạm phi ngữ cảnh - các quy tắc là quy tắc phi
ngữ cảnh⇒ sinh ngôn ngữ phi ngữ cảnh
Kiểu 1: Văn phạm cảm ngữ cảnh - các quy tắc là quy tắc
cảm ngữ cảnh⇒ sinh ngôn ngữ cảm ngữ cảnh
Kiểu 0: Văn phạm không hạn chế/tổng quát - các quy tắc là
quy tắc tổng quát⇒ sinh ngôn ngữ tổng quát
L0 ⊃ L1 ⊃ L2 ⊃ L3
Ch1. NN&VP hình thức 23 / 30
Văn phạm hình thức
Phân lớp văn phạm của Chomsky (2)
Các lớp văn phạm
Kiểu 3: Văn phạm chính quy - các quy tắc là quy tắc tuyến
tính phải⇒ sinh ngôn ngữ chính quy
Kiểu 2: Văn phạm phi ngữ cảnh - các quy tắc là quy tắc phi
ngữ cảnh⇒ sinh ngôn ngữ phi ngữ cảnh
Kiểu 1: Văn phạm cảm ngữ cảnh - các quy tắc là quy tắc
cảm ngữ cảnh⇒ sinh ngôn ngữ cảm ngữ cảnh
Kiểu 0: Văn phạm không hạn chế/tổng quát - các quy tắc là
quy tắc tổng quát⇒ sinh ngôn ngữ tổng quát
L0 ⊃ L1 ⊃ L2 ⊃ L3
Ch1. NN&VP hình thức 23 / 30
Văn phạm hình thức
Phân lớp văn phạm của Chomsky (2)
Các lớp văn phạm
Kiểu 3: Văn phạm chính quy - các quy tắc là quy tắc tuyến
tính phải⇒ sinh ngôn ngữ chính quy
Kiểu 2: Văn phạm phi ngữ cảnh - các quy tắc là quy tắc phi
ngữ cảnh⇒ sinh ngôn ngữ phi ngữ cảnh
Kiểu 1: Văn phạm cảm ngữ cảnh - các quy tắc là quy tắc
cảm ngữ cảnh⇒ sinh ngôn ngữ cảm ngữ cảnh
Kiểu 0: Văn phạm không hạn chế/tổng quát - các quy tắc là
quy tắc tổng quát⇒ sinh ngôn ngữ tổng quát
L0 ⊃ L1 ⊃ L2 ⊃ L3
Ch1. NN&VP hình thức 23 / 30
Văn phạm hình thức
Phân lớp văn phạm của Chomsky (2)
Các lớp văn phạm
Kiểu 3: Văn phạm chính quy - các quy tắc là quy tắc tuyến
tính phải⇒ sinh ngôn ngữ chính quy
Kiểu 2: Văn phạm phi ngữ cảnh - các quy tắc là quy tắc phi
ngữ cảnh⇒ sinh ngôn ngữ phi ngữ cảnh
Kiểu 1: Văn phạm cảm ngữ cảnh - các quy tắc là quy tắc
cảm ngữ cảnh⇒ sinh ngôn ngữ cảm ngữ cảnh
Kiểu 0: Văn phạm không hạn chế/tổng quát - các quy tắc là
quy tắc tổng quát⇒ sinh ngôn ngữ tổng quát
L0 ⊃ L1 ⊃ L2 ⊃ L3
Ch1. NN&VP hình thức 23 / 30
Hai bài toán cơ bản về văn phạm
Nội dung
1. Bảng chữ cái – Từ – Ngôn ngữ
2. Các phép toán trên từ
3. Các phép toán trên ngôn ngữ
4. Văn phạm hình thức
5. Hai bài toán cơ bản về văn phạm
Bài toán phân tích
Bài toán tổng hợp
Ch1. NN&VP hình thức 24 / 30
Hai bài toán cơ bản về văn phạm Bài toán phân tích
Bài toán phân tích
Cho một văn phạm hình thức. Xác định ngôn ngữ sinh bởi
văn phạm đó.
Ch1. NN&VP hình thức 25 / 30
Hai bài toán cơ bản về văn phạm Bài toán phân tích
Bài tập
Tìm các ngôn ngữ sinh bởi các văn phạm có tập quy tắc
như sau
1. S → aA (1), A→ aA (2), A→ bB (3), B → bB (4), B → cC
(5), B → c (6), C → cC (7), C → c (8)
2. S → aSb (1), S → ab (2)
3. S → aSBC (1), S → aBC (2), aB → ab (3), bB → bb (4),
CB → BC (5), bC → bc (6), cC → cc (7)
Ch1. NN&VP hình thức 26 / 30
Hai bài toán cơ bản về văn phạm Bài toán phân tích
Bài tập
Tìm các ngôn ngữ sinh bởi các văn phạm có tập quy tắc
như sau
1. S → aA (1), A→ aA (2), A→ bB (3), B → bB (4), B → cC
(5), B → c (6), C → cC (7), C → c (8)
2. S → aSb (1), S → ab (2)
3. S → aSBC (1), S → aBC (2), aB → ab (3), bB → bb (4),
CB → BC (5), bC → bc (6), cC → cc (7)
Ch1. NN&VP hình thức 26 / 30
Hai bài toán cơ bản về văn phạm Bài toán phân tích
Bài tập
Tìm các ngôn ngữ sinh bởi các văn phạm có tập quy tắc
như sau
1. S → aA (1), A→ aA (2), A→ bB (3), B → bB (4), B → cC
(5), B → c (6), C → cC (7), C → c (8)
2. S → aSb (1), S → ab (2)
3. S → aSBC (1), S → aBC (2), aB → ab (3), bB → bb (4),
CB → BC (5), bC → bc (6), cC → cc (7)
Ch1. NN&VP hình thức 26 / 30
Hai bài toán cơ bản về văn phạm Bài toán tổng hợp
Bài toán tổng hợp
Cho một ngôn ngữ. Xây dựng văn phạm sinh ngôn ngữ đó.
Ch1. NN&VP hình thức 27 / 30
Hai bài toán cơ bản về văn phạm Bài toán tổng hợp
Bài tập
Xây dựng văn phạm sinh các ngôn ngữ sau
1. {anbmcpdq | n,m ≥ 0,p ≥ 1,q ≥ 2}
2. {0,1}+ và {0,1}∗
3. {xx˜ | x ∈ {a,b, c}∗}
4. {anbmc2nxdpx˜ | n,m ≥ 0,p ≥ 2, x ∈ {a,b, c}+}
5. Tập các tên (identifier) trong ngôn ngữ lập trình
6. Tập các số tự nhiên. Tập các số nguyên
7. Tập các biểu thức số học trên tập số thực
Ch1. NN&VP hình thức 28 / 30
Hai bài toán cơ bản về văn phạm Bài toán tổng hợp
Bài tập
Xây dựng văn phạm sinh các ngôn ngữ sau
1. {anbmcpdq | n,m ≥ 0,p ≥ 1,q ≥ 2}
2. {0,1}+ và {0,1}∗
3. {xx˜ | x ∈ {a,b, c}∗}
4. {anbmc2nxdpx˜ | n,m ≥ 0,p ≥ 2, x ∈ {a,b, c}+}
5. Tập các tên (identifier) trong ngôn ngữ lập trình
6. Tập các số tự nhiên. Tập các số nguyên
7. Tập các biểu thức số học trên tập số thực
Ch1. NN&VP hình thức 28 / 30
Hai bài toán cơ bản về văn phạm Bài toán tổng hợp
Bài tập
Xây dựng văn phạm sinh các ngôn ngữ sau
1. {anbmcpdq | n,m ≥ 0,p ≥ 1,q ≥ 2}
2. {0,1}+ và {0,1}∗
3. {xx˜ | x ∈ {a,b, c}∗}
4. {anbmc2nxdpx˜ | n,m ≥ 0,p ≥ 2, x ∈ {a,b, c}+}
5. Tập các tên (identifier) trong ngôn ngữ lập trình
6. Tập các số tự nhiên. Tập các số nguyên
7. Tập các biểu thức số học trên tập số thực
Ch1. NN&VP hình thức 28 / 30
Hai bài toán cơ bản về văn phạm Bài toán tổng hợp
Bài tập
Xây dựng văn phạm sinh các ngôn ngữ sau
1. {anbmcpdq | n,m ≥ 0,p ≥ 1,q ≥ 2}
2. {0,1}+ và {0,1}∗
3. {xx˜ | x ∈ {a,b, c}∗}
4. {anbmc2nxdpx˜ | n,m ≥ 0,p ≥ 2, x ∈ {a,b, c}+}
5. Tập các tên (identifier) trong ngôn ngữ lập trình
6. Tập các số tự nhiên. Tập các số nguyên
7. Tập các biểu thức số học trên tập số thực
Ch1. NN&VP hình thức 28 / 30
Hai bài toán cơ bản về văn phạm Bài toán tổng hợp
Bài tập
Xây dựng văn phạm sinh các ngôn ngữ sau
1. {anbmcpdq | n,m ≥ 0,p ≥ 1,q ≥ 2}
2. {0,1}+ và {0,1}∗
3. {xx˜ | x ∈ {a,b, c}∗}
4. {anbmc2nxdpx˜ | n,m ≥ 0,p ≥ 2, x ∈ {a,b, c}+}
5. Tập các tên (identifier) trong ngôn ngữ lập trình
6. Tập các số tự nhiên. Tập các số nguyên
7. Tập các biểu thức số học trên tập số thực
Ch1. NN&VP hình thức 28 / 30
Hai bài toán cơ bản về văn phạm Bài toán tổng hợp
Bài tập
Xây dựng văn phạm sinh các ngôn ngữ sau
1. {anbmcpdq | n,m ≥ 0,p ≥ 1,q ≥ 2}
2. {0,1}+ và {0,1}∗
3. {xx˜ | x ∈ {a,b, c}∗}
4. {anbmc2nxdpx˜ | n,m ≥ 0,p ≥ 2, x ∈ {a,b, c}+}
5. Tập các tên (identifier) trong ngôn ngữ lập trình
6. Tập các số tự nhiên. Tập các số nguyên
7. Tập các biểu thức số học trên tập số thực
Ch1. NN&VP hình thức 28 / 30
Hai bài toán cơ bản về văn phạm Bài toán tổng hợp
Bài tập
Xây dựng văn phạm sinh các ngôn ngữ sau
1. {anbmcpdq | n,m ≥ 0,p ≥ 1,q ≥ 2}
2. {0,1}+ và {0,1}∗
3. {xx˜ | x ∈ {a,b, c}∗}
4. {anbmc2nxdpx˜ | n,m ≥ 0,p ≥ 2, x ∈ {a,b, c}+}
5. Tập các tên (identifier) trong ngôn ngữ lập trình
6. Tập các số tự nhiên. Tập các số nguyên
7. Tập các biểu thức số học trên tập số thực
Ch1. NN&VP hình thức 28 / 30
Hai bài toán cơ bản về văn phạm Bài toán tổng hợp
Tính nhập nhằng của văn phạm
So sánh 2 văn phạm sinh biểu thức số học
E → N | E + E | E − E | E ∗ E | E/E | (E)
N → 1 | 2 | 3
E → T | E + T | E − T
T → F | T ∗ F | T/F
F → N | (E)
N → 1 | 2 | 3
Dẫn xuất cho 1 + 2 ∗ 3 ???
Cây dẫn xuất
Ch1. NN&VP hình thức 29 / 30
Hai bài toán cơ bản về văn phạm Bài toán tổng hợp
Tính nhập nhằng của văn phạm
So sánh 2 văn phạm sinh biểu thức số học
E → N | E + E | E − E | E ∗ E | E/E | (E)
N → 1 | 2 | 3
E → T | E + T | E − T
T → F | T ∗ F | T/F
F → N | (E)
N → 1 | 2 | 3
Dẫn xuất cho 1 + 2 ∗ 3 ???
Cây dẫn xuất
Ch1. NN&VP hình thức 29 / 30
Hai bài toán cơ bản về văn phạm Bài toán tổng hợp
Tính nhập nhằng của văn phạm
So sánh 2 văn phạm sinh biểu thức số học
E → N | E + E | E − E | E ∗ E | E/E | (E)
N → 1 | 2 | 3
E → T | E + T | E − T
T → F | T ∗ F | T/F
F → N | (E)
N → 1 | 2 | 3
Dẫn xuất cho 1 + 2 ∗ 3 ???
Cây dẫn xuất
Ch1. NN&VP hình thức 29 / 30
Hai bài toán cơ bản về văn phạm Bài toán tổng hợp
Bài tập bổ sung
Xây dựng văn phạm tuyến tính trái sinh tập các tên
Ch1. NN&VP hình thức 30 / 30