PDA & Ngữ pháp không theo ngữ cảnh
Nếu một ngữ pháp G không có ngữ cảnh, chúng tôi có thể xây dựng một PDA không xác định tương đương chấp nhận ngôn ngữ được tạo ra bởi ngữ pháp không có ngữ cảnh G. Một trình phân tích cú pháp có thể được xây dựng cho ngữ phápG.
Còn nếu P là một trình tự động đẩy xuống, một ngữ pháp tương đương không có ngữ cảnh G có thể được xây dựng ở đó
L(G) = L(P)
Trong hai chủ đề tiếp theo, chúng ta sẽ thảo luận về cách chuyển đổi từ PDA sang CFG và ngược lại.
Thuật toán tìm PDA tương ứng với CFG cho trước
Input - Một CFG, G = (V, T, P, S)
Output- PDA tương đương, P = (Q, ∑, S, δ, q 0 , I, F)
Step 1 - Chuyển đổi các sản phẩm của CFG thành GNF.
Step 2 - PDA sẽ chỉ có một trạng thái {q}.
Step 3 - Biểu tượng bắt đầu của CFG sẽ là biểu tượng bắt đầu trong PDA.
Step 4 - Tất cả các thiết bị đầu cuối không phải của CFG sẽ là ký hiệu ngăn xếp của PDA và tất cả các thiết bị đầu cuối của CFG sẽ là ký hiệu đầu vào của PDA.
Step 5 - Đối với mỗi lần sản xuất theo mẫu A → aX nơi a là thiết bị đầu cuối và A, X là sự kết hợp của thiết bị đầu cuối và không thiết bị đầu cuối, hãy thực hiện chuyển đổi δ (q, a, A).
Vấn đề
Xây dựng PDA từ CFG sau.
G = ({S, X}, {a, b}, P, S)
nơi sản xuất -
S → XS | ε , A → aXb | Ab | ab
Giải pháp
Để PDA tương đương,
P = ({q}, {a, b}, {a, b, X, S}, δ, q, S)
ở đâu δ -
δ (q, ε, S) = {(q, XS), (q, ε)}
δ (q, ε, X) = {(q, aXb), (q, Xb), (q, ab)}
δ (q, a, a) = {(q, ε)}
δ (q, 1, 1) = {(q, ε)}
Thuật toán tìm CFG tương ứng với PDA cho trước
Input - Một CFG, G = (V, T, P, S)
Output- PDA tương đương, P = (Q, ∑, S, δ, q 0 , I, F) sao cho các đầu cuối của văn phạm G sẽ là {X wx | w, x ∈ Q} và trạng thái khởi đầu sẽ là Một q0, F .
Step 1- Với mọi w, x, y, z ∈ Q, m ∈ S và a, b ∈ ∑, nếu δ (w, a, ε) chứa (y, m) và (z, b, m) chứa (x, ε), thêm quy tắc sản xuất X wx → a X yz b trong ngữ pháp G.
Step 2- Với mọi w, x, y, z ∈ Q, thêm quy tắc sản xuất X wx → X wy X yx trong văn phạm G.
Step 3- Với w ∈ Q, thêm quy tắc sản xuất X ww → ε trong văn phạm G.