intTypePromotion=1

Bài giảng Ngôn ngữ hình thức: Phần 2 - ĐH Sư phạm kỹ thuật Nam Định

Chia sẻ: Ermintrudetran Ermintrudetran | Ngày: | Loại File: PDF | Số trang:140

0
7
lượt xem
1
download

Bài giảng Ngôn ngữ hình thức: Phần 2 - ĐH Sư phạm kỹ thuật Nam Định

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tiếp nội dung phần 1, Bài giảng Ngôn ngữ hình thức: Phần 2 cung cấp cho người học những kiến thức như: Trình bày các kiến thức cơ bản về: Văn phạm phi ngữ cảnh (CFG); rút gọn văn phạm phi ngữ cảnh; chuẩn hoá văn phạm phi ngữ cảnh; tính chất của văn phạm phi ngữ cảnh; automat đẩy xuống (PDA); sự tương đương của PDA và CFG.

Chủ đề:
Lưu

Nội dung Text: Bài giảng Ngôn ngữ hình thức: Phần 2 - ĐH Sư phạm kỹ thuật Nam Định

  1. Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống Chƣơng 3. VĂN PHẠM PHI NGỮ CẢNH VÀ AUTOMAT ĐẨY XUỐNG (Contexet free Grammar - CFG and push down Automata - PDA) Mục tiêu: Giúp sinh viên có khả năng: - Hiểu đƣợc khái niệm và xác định đƣợc các thành phần của một CFG. - Nhận dạng đƣợc lớp ngôn ngữ phi ngữ cảnh (CFL) do văn phạm CFG sinh ra và tính chất của CFL. - Xây dựng đƣợc các thành phần của CFG đặc tả một lớp CFL. - Hiểu và xây dựng đƣợc dẫn xuất và cây dẫn xuất. - Rút gọn và chuẩn hoá đƣợc CFG. - Hiểu đƣợc khái niệm và xác định đƣợc các thành phần của một PDA - Xây dựng đƣợc các thành phần của PDA đoán nhận ngôn ngữ sinh bởi CFG và xây dựng đƣợc CFG sinh ra ngôn ngữ đƣợc đoán nhận bởi PDA. Nội dung chính: - Văn phạm phi ngữ cảnh: định nghĩa, dẫn xuất và ngôn ngữ và cây dẫn xuất. - Rút gọn văn phạm phi ngữ cảnh. - Chuẩn hoá văn phạm phi ngữ cảnh. - Tính chất của CFL. - Automat đẩy xuống: định nghĩa, ngôn ngữ đoán nhận bởi PDA. - Quan hệ của PDA và CFG. 3.1. Văn phạm phi ngữ cảnh (CFG: Context Free Grammar) Xuất xứ của văn phạm phi ngữ cảnh là sự mô tả thông qua các ngôn ngữ tự nhiên. Ta có thể viết các quy tắc cú pháp để diễn tả câu “An là sinh viên giỏi“ nhƣ sau: < câu đơn > → < chủ ngữ > < vị ngữ > < chủ ngữ > → < danh từ > < vị ngữ > → < động từ > < bổ ngữ > < bổ ngữ > → < danh từ > < tính từ > 107 Phạm Hùng Phú
  2. Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống < danh từ > → An < danh từ > → sinh viên < động từ > → là < tính từ > → giỏi Các từ trong cặp dấu < > nhƣ , , , ... là các phạm trù cú pháp, cho ta vai trò của các bộ phận hợp thành câu. Ta thấy một câu đƣợ sinh ra qua các bƣớc triển khai dần dần theo các quy tắc cú pháp. Đây cũng chính là dạng của các luật sinh trong văn phạm phi ngữ cảnh. Nhƣ vậy, văn phạm phi ngữ cảnh cũng có thể chọn làm mô hình cho các văn phạm của các ngôn ngữ tự nhiên. Tuy nhiên, trong khoa học máy tính, với nhu cầu biểu diễn các ngôn ngữ lập trình, văn phạm phi ngữ cảnh CFG còn đƣợc thiết kế thành một dạng tƣơng đƣơng gọi là văn phạm BNF (Backus - Naur Form). Đây cũng là văn phạm CFG với những thay đổi nhỏ về dạng thức và một số ký hiệu viết tắt mà các nhà khoa học máy tính thƣờng ứng dụng trong việc diễn tả cú pháp của các ngôn ngữ lập trình cấp cao (nhƣ ALGOL, PASCAL, ... ). Trong dạng thức của văn phạm BNF, ký hiệu::= đƣợc dùng thay cho ký hiệu →. Chẳng hạn, để định nghĩa một biểu thức số học (expression) bao gồm các danh biểu (identifier) tham gia vào các phép toán +, * hoặc biểu thức con lồng trong dấu ngoặc đơn , ta viết: ::= + ::= * ::= ( ) ::= Việc nghiên cứu các văn phạm phi ngữ cảnh đã tạo nên một cơ sở lý luận vững chắc cho việc biểu diễn ngôn ngữ lập trình, việc tìm kiếm các giải thuật phân tích cú pháp vận dụng trong chƣơng trình dịch và cho nhiều ứng dụng khác về xử lý xâu. Chẳng hạn, nó rất hữu ích trong việc mô tả các biểu thức số học với nhiều dấu ngoặc lồng nhau hoặc cấu trúc khối trong ngôn ngữ lập trình có cấu trúc mà biểu thức chính quy không thể đặc tả đƣợc. Văn phạm phi ngữ cảnh là một tập hợp hữu hạn các biến (còn gọi là các ký hiệu chưa kết thúc), mỗi biến biểu diễn một ngôn ngữ. Ngôn ngữ đƣợc biểu diễn bởi 108 Phạm Hùng Phú
  3. Câu hỏi và bài tập chƣơng 3 các biến đƣợc mô tả một cách đệ quy theo thuật ngữ của một khái niệm khác gọi là ký hiệu kết thúc. Quy tắc quan hệ giữa các biến và các ký hiệu kết thúc đƣợc gọi là luật sinh. Mỗi luật sinh có dạng một biến ở vế trái sinh ra một xâu có thể gồm các biến lẫn các ký hiệu kết thúc trong văn phạm. 3.1.1. Định nghĩa Văn phạm phi ngữ cảnh (CFG) là một hệ thống gồm bốn thành phần, ký hiệu là G = (N, T, P, S); trong đó: - N là tập hữu hạn các ký tự không kết thúc (hay các biến) ; - T là tập hữu hạn các ký tự kết thúc; N  T = ∅ ; - P là tập hữu hạn các luật sinh mà mỗi luật sinh có dạng A → α với A  N và α  (N  T)*; - S là một ký tự không kết thúc đặc biệt gọi là ký tự bắt đầu văn phạm. Ví dụ: Văn phạm phi ngữ cảnh G = (N, T, P, S); trong đó: N = {S, A, B}; T = {a, b}; S = S; P gồm các luật sinh sau: S → AB; A → aA; A → a; B → bB; B → b. Quy ƣớc ký hiệu: - Các chữ in hoa A, B, C, D, E, ... đầu bảng chữ cái La tinh và S ký hiệu cho các ký tự không kết thúc (S thƣờng đƣợc dùng làm ký tự bắt đầu ). - Các chữ nhỏ a, b, c, d, e, ..., các chữ số và một số ký tự khác ký hiệu cho các ký tự kết thúc. - Các chữ in hoa X, Y, Z ký hiệu cho các ký tự có thể kết thúc hoặc không kết thúc. Phạm Hùng Phú 109
  4. Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống - Các chữ Hi-Lạp α, β, γ, ... ký hiệu cho các xâu gồm các ký tự kết thúc và không kết thúc. Ta sẽ biểu diễn văn phạm một cách tóm tắt bằng cách chỉ liệt kê các luật sinh của nó. Nếu A → α ; A → α ; ... ; A → α là các luật sinh của biến A trong văn 1 2 k phạm nào đó, ta sẽ ghi ngắn gọn là A → α | α | ... | α 1 2 k Ví dụ: Văn phạm cho trong ví dụ trên có thể viết gọn là: S → AB; A → aA | a; B → bB | b‟ 3.1.2. Dẫn xuất và ngôn ngữ 1) Dẫn xuất Cho văn phạm CFG: G = (N, T, P, S), giả sử luật sinh A → β  P và xâu αAγ  (N T)* với α , β, γ  (N T)* . Nếu thay ký tự không kết thúc A trong xâu αAγ bằng xâu β để thu đƣợc xâu αβγ hay còn nói áp dụng luật sinh A → β vào xâu αAγ để thu đƣợc xâu αβγ; khi đó, ta nói rằng xâu αAγ dẫn xuất trực tiếp ra xâu αβγ hay xâu αβγ đƣợc dẫn xuất trực tiếp từ xâu αAγ trong văn phạm G và đƣợc ký hiệu là αAγ  αβγ. G Giả sử α , α , ..., α là các xâu thuộc (N  T)* với m ≥ 1 và 1 2 m α  α ; α  α ; …; α  α 1 G 2 2 G 3 m -1 G m thì ta ký hiệu là α * α và nói là α dẫn xuất (không, một hoặc nhiều bƣớc) ra α 1 G m 1 m hay α đƣợc dẫn xuất từ α trong văn phạm G. m 1 Nếu α dẫn xuất ra α bằng i bƣớc dẫn xuất thì ta ký hiệu là α i α . 1 m 1 G m Nếu α dẫn xuất ra α bằng một hoặc nhiều bƣớc dẫn xuất thì ta ký hiệu là 1 m α + α . 1 G m Chú ý rằng α * α với mọi xâu α. và nếu α * ;  *  thì α *  với G G G G mọi xâu α, , . 110 Phạm Hùng Phú
  5. Câu hỏi và bài tập chƣơng 3 Thông thƣờng, nếu không có nhầm lẫn, ta sẽ dùng các ký hiệu  , *, + i thay cho ký hiệu tƣơng ứng  , * , + , i . G G G G 2) Ngôn ngữ sinh bởi văn phạm phi ngữ cảnh Cho văn phạm CFG: G = (N, T, P, S), Ngôn ngữ sinh bởi văn phạm phi ngữ * cảnh G là L(G) = {w | w  T và S * w} và đƣợc gọi là ngôn ngữ phi ngữ cảnh. G Nghĩa là, một xâu thuộc L(G) nếu: 1. Xâu gồm toàn ký tự kết thúc. 2. Xâu đƣợc dẫn xuất ra từ ký tự bắt đầu S. Xâu α gồm các ký tự kết thúc và các ký tự không kết thúc, đƣợc gọi là một dạng câu sinh từ văn phạm G nếu S * α . G Hai văn phạm phi ngữ cảnh G , G đƣợc gọi là tƣơng đƣơng nếu L(G ) = L(G ). 1 2 1 2 Ví dụ: 1. Xét văn phạm CLG: G = (N, T, P, S), trong đó: N = {S}; T = {a, b}; P = {S → aSb, S → ab}. Bằng cách áp dụng luật sinh thứ nhất n-1 lần và luật sinh thứ hai 1 lần, ta có: 3 3 n-1 n-1 n n S  aSb  aaSbb  a Sb  ...  a b a b n n n n Vậy, L(G) chứa các xâu có dạng a b với n ≥ 1; hay L(G) = {a b | n ≥ 1}. 2. Xét văn phạm CLG: G‟ = (N‟, T, P‟, S), trong đó: N‟ = {S, A}; T = {a, b}; P‟ = {S → aAb; A → aAb; A → }. Bằng cách áp dụng luật sinh thứ nhất 1 lần, luật sinh thứ hai n -1 lần và luật sinh thứ ba 1 lần , ta có: 3 3 n-1 n-1 n n n n S  aAb  aaAbb  a Ab  ...  a Ab  a Ab  a b n n n n Vậy, L(G‟) chứa các xâu có dạng a b với n ≥ 1; hay L(G‟) = {a b | n ≥ 1}. Và ta có L(G) =L(G‟) nên hai văn phạm phi ngữ cảnh trên là tƣơng đƣơng. 3.1.3. Cây dẫn xuất Để hình dung một cách trực quan việc sinh ra các xâu trong văn phạm phi ngữ cảnh, ngƣời ta thƣờng diễn tả một dãy dẫn xuất qua hình ảnh một cây. Một cách hình thức, ta định nghĩa cây dẫn xuất nhƣ sau: 1) Định nghĩa Phạm Hùng Phú 111
  6. Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống Cho văn phạm CFG: G = (N, T, P, S). Cây dẫn xuất (hay cây phân tích cú pháp) của G đƣợc định nghĩa nhƣ sau: 1. Mỗi nút có một nhãn, là một ký tự  (N T{ε}). 2. Nút gốc có nhãn là ký tự bắt đầu S. 3. Nếu nút trong (trung gian) có nhãn A thì A  N. 4. Nếu nút n có nhãn A và các nút n , n , ..., n là con của n theo thứ tự từ trái 1 2 k sang phải có nhãn lần lƣợt là X , X , ..., X thì A → X X ... X là một luật sinh 1 2 k 1 2 k trong tập luật sinh P. 5. Nếu nút n có nhãn là từ rỗng ε thì n phải là nút lá và là nút con duy nhất của nút cha của nó. 2) Ví dụ: a) Cho văn phạm G = ({S, A}, {a, b}, P, S), trong đó P gồm: S → aAS | a; A → SbA | SS | ba. Một cây dẫn xuất từ văn phạm có dạng nhƣ sau: S S a A a S b A a b a Hình 3.1. Cây dẫn xuất từ văn phạm Ta thấy, nút 1 có nhãn S và các con của nó lần lƣợt là a, A, S (chú ý S → aAS là một luật sinh). Tƣơng tự, nút 3 có nhãn A và các con của nó là S, b, A (từ luật sinh A → SbA). Nút 4, 5 có cùng nhãn S và có nút con nhãn a (luật sinh S → a). Cuối cùng nút 7 có nhãn A và có các nút con b, a (luật sinh A → ba). Trên cây dẫn xuất, nếu ta đọc các lá theo thứ tự từ “trái sang phải“ thì ta có một dạng câu trong G. Ta gọi xâu này là xâu sinh bởi cây dẫn xuất. 112 Phạm Hùng Phú
  7. Câu hỏi và bài tập chƣơng 3 Một cây con (subtree) của cây dẫn xuất có nút gốc nhãn là A còn đƣợc gọi là A-cây con (hoặc A-cây). Cây con cũng giống nhƣ cây dẫn xuất, chỉ khác là nhãn của nút gốc không nhất thiết phải là ký tự bắt đầu S. b) Xét văn phạm và cây dẫn xuất trên. Đọc các lá theo thứ tự từ trái sang phải ta có xâu aabbaa. Trong trƣờng hợp này, tất cả các lá đều là ký tự kết thúc. Tuy nhiên, nói chung cũng không bắt buộc nhƣ thế; lá có thể có nhãn là ε hoặc biến. Ta thấy dẫn xuất S * aabbaa bằng dãy dẫn xuất: S  aAS  aSbAS  aabAS  aabbaS  aabbaa. A-cây (nút 3) nhãn của nút gốc là A tạo ra xâu con abba theo dãy dẫn xuất: A  SbA  abA  abba. 3.1.4. Quan hệ giữa dẫn xuất và cây dẫn xuất 1) Định lý Cho G = (N, T, P, S) là một văn phạm phi ngữ cảnh. S * α  tồn tại cây dẫn xuất trong văn phạm G sinh ra α từ S. Chứng minh: Ta chứng minh rằng với biến A bất kỳ, A * α  có một A-cây sinh ra α. - Đảo: Giả sử α đƣợc sinh bởi A-cây, ta chứng minh quy nạp theo số nút trong của cây dẫn xuất rằng A * α. Nếu A có số nút trong là 1 thì cây phải có dạng nhƣ hình sau: Khi đó X X ... X là xâu α và A → α là một luật sinh trong P theo định nghĩa cây 1 2 n dẫn xuất. S X1 X2 ... Xn Hình 3.2(a). A-cây với một nút trong Giả sử kết quả đúng tới số nút trong là k -1 ( k > 1) Ta chứng minh kết quả cũng đúng với số nút trong là k. Phạm Hùng Phú 113
  8. Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống Xét α đƣợc sinh ra bởi A-cây có số nút trong là k. Rõ ràng các nút con của nút gốc không phải tất cả đều là lá, ta gọi chúng từ trái sang phải là X , X , ..., X thì 1 2 n chắc chắn rằng A → X X ... X là một luật sinh. Xét nút X bất kỳ: 1 2 n i + Nếu X không là nút lá thì X phải là một biến và X - cây con sẽ sinh ra một i i i xâu α nào đó. i + Nếu X là nút lá, ta đặt α = X . Dễ thấy rằng nếu j < i thì các α ở bên trái α , do i i i j j vậy xâu đọc từ lá vẫn có dạng α = α α ... α . Mỗi X - cây con phải có ít nút trong hơn 1 2 n i cây ban đầu, vì thế theo giả thiết quy nạp, với mỗi đỉnh i không phải là lá thì X * α . i i Vậy A  X X ... X * α X ... X * α α X ... X * ... * α α ... α = α 1 2 n 1 2 n 1 2 3 n 1 2 n Hay ta có A * α . Chú ý rằng đây chỉ là một trong nhiều cách dẫn xuất ra α. - Thuận: giả sử A * α , ta cần chỉ ra một A - cây sinh ra α. Nếu A * α bằng một bƣớc dẫn xuất thì A → α là một luật sinh trong P và có cây dẫn xuất sinh ra α nhƣ trong hình trên. Giả sử kết quả đúng tới k-1 bƣớc dẫn xuất Xét A * α bằng k bƣớc dẫn xuất, gọi bƣớc đầu tiên là A → X X ... X . 1 2 n Rõ ràng, một ký tự trong α phải đƣợc dẫn ra từ một biến X nào đó. Vì vậy, ta i có thể viết α = α α ... α , trong đó mỗi 1 ≤ i ≤ n thoả mãn: 1 2 n + α = X nếu X là ký tự kết thúc. i i i + X * α nếu X là một biến (ký tự không kết thúc). i i i Nếu X là biến thì dẫn xuất của α từ X phải có ít hơn k bƣớc. Vì vậy, theo giả i i i thiết quy nạp ta có X - cây sinh ra α , đặt cây này là T i i i Bây giờ ta dựng A - cây có n lá X X ... X . Mỗi X không là ký tự kết thúc ta 1 2 n i thay bằng cây T tƣơng ứng. Cuối cùng, ta có cây dẫn xuất sinh ra có dạng nhƣ sau: i 114 Phạm Hùng Phú
  9. Câu hỏi và bài tập chƣơng 3 S X3 ... Xn-1 X1 X2 Xn T2 T3 Tn Hình 3.2(b). A-cây 2) Ví dụ: Xét dãy dẫn xuất S * aabbaa của văn phạm trên Bƣớc đầu tiên trong dẫn xuất đó là S  aAS. Theo dõi các bƣớc suy dẫn sau đó, ta thấy biến A đƣợc thay bởi SbA, rồi trở thành abA và cuối cùng thành abba, đó chính là kết quả của cây T (A - cây). Còn biến S thì đƣợc thay bởi a và đó là kết 2 quả của cây T (S -cây). Ghép nối lại, ta đƣợc cây dẫn xuất mà kết quả là xâu 3 aabbaa. S S S a A S S b A a T2 T3 b a Cây T2 Cây T3 Hình 3.3. Ghép nối các cây dẫn xuất 3.1.5. Dẫn xuất trái nhất, dẫn xuất phải nhất 1) Định nghĩa Nếu tại mỗi bƣớc dẫn xuất, luật sinh đƣợc áp dụng vào biến bên trái nhất thì ta gọi đó là dẫn xuất trái nhất (leftmost - lm) hay dẫn xuất trái. Tƣơng tự, nếu biến bên phải nhất đƣợc thay thế ở mỗi bƣớc dẫn xuất thì đó là dẫn xuất phải nhất (rightmost - rm) hay dẫn xuất phải. Nếu xâu w  L(G) với CFG G thì w sẽ có ít nhất một cây dẫn xuất ra nó và tƣơng ứng với các cây này, w chỉ có duy nhất một dẫn xuất trái nhất và duy nhất Phạm Hùng Phú 115
  10. Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống một dẫn xuất phải nhất. Dĩ nhiên, w có thể có nhiều dẫn xuất trái (phải) nhất vì nó có thể có nhiều cây dẫn xuất. 2) Ví dụ: Xét cây dẫn xuất ở hình 3.1 - Dẫn xuất trái nhất của cây: S  aAS  aSbAS  aabAS  aabbaS  aabbaa. -Dẫn xuất phải nhất tƣơng ứng là: S  aAS  aAa  aSbAa  aSbbaa  aabbaa. 3.1.6. Văn phạm nhập nhằng (mơ hồ) 1) Định nghĩa Một văn phạm phi ngữ cảnh G có nhiều hơn một cây dẫn xuất trái nhất hay phải nhất cho cùng một xâu w thì G đƣợc gọi là văn phạm nhập nhằng (ambiguity). Dĩ nhiên, cũng có thể nói rằng văn phạm G là nhập nhằng nếu có một xâu w đƣợc dẫn ra từ ký tự bắt đầu S với hai dẫn xuất trái nhất hoặc hai dẫn xuất phải nhất. 2) Ví dụ Xét văn phạm phi ngữ cảnh G với các luật sinh nhƣ sau: E→E+E|E*E|(E)|a Văn phạm này sinh ra các xâu biểu thức số học với 2 phép toán + và * . Xét xâu a + a * a , xâu này có hai dẫn xuất trái nhất là: 1. E  E + E  a + E  a + E * E  a + a * E  a + a * a 2. E  E * E  E + E *E  a + E * E  a + a * E  a + a * a Và có hai cây dẫn xuất trái nhất tƣơng ứng là: E E E + E E E * E E E a * E + a a a a a a) b) Hình 3.4. Hai cây dẫn xuất trái nhất cho cùng xâu 116 Phạm Hùng Phú
  11. Câu hỏi và bài tập chƣơng 3 Vậy văn phạm trên là văn phạm nhập nhằng. Điều này có nghĩa là biểu thức a + a * a có thể hiểu theo hai cách khác nhau: thực hiện phép cộng trƣớc hay phép nhân trƣớc ? Để khắc phục sự nhập nhằng này, ta có thể: - Hoặc quy định rằng các phép cộng và nhân luôn luôn đƣợc thực hiện theo thứ tự từ trái sang phải (trừ khi gặp ngoặc đơn). Ta viết văn phạm G không mơ hồ 1 tƣơng đƣơng nhƣ sau: E→E+T|E*T|T; T→(E)|a. - Hoặc quy định rằng khi không có dấu ngoặc đơn ngăn cách thì phép nhân luôn luôn đƣợc ƣu tiên hơn phép cộng. Ta viết văn phạm G không mơ hồ tƣơng 2 đƣơng nhƣ sau: E → E + T | T; T → T * F | F; F → ( E ) | a. 3.2. Rút gọn văn phạm phi ngữ cảnh Thông thƣờng, một văn phạm phi ngữ cảnh có thể còn chứa đựng một vài yếu tố thừa. Chẳng hạn nhƣ theo các đặc tính trên, có những ký tự không thực sự tham gia vào quá trình dẫn xuất ra xâu, hoặc sẽ có những luật sinh dạng A → B làm kéo dài dãy dẫn xuất một cách không cần thiết. Vì vậy, việc rút gọn văn phạm phi ngữ cảnh là nhằm loại bỏ những yếu tố thừa đó mà không làm giảm bớt khả năng sản sinh ngôn ngữ của văn phạm. Nếu L là một CFL, nó có thể tạo ra văn phạm CFG với các đặc tính sau: 1. Mỗi biến và mỗi ký tự kết thúc của G đều xuất hiện trong dẫn xuất của một số xâu trong L. 2. Không có luật sinh nào dạng A → B, mà trong đó A, B đều là biến. Hơn nữa, nếu ε ∉ L thì không cần luật sinh A → ε. Thực tế, nếu ε ∉ L, ta có mọi luật sinh trong G đều có một trong hai dạng: A → BC và A → a với A, B, C  N; aT Phạm Hùng Phú 117
  12. Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống hoặc A → aα (α là xâu các biến hoặc ε). Hai dạng đặc biệt này gọi là dạng chuẩn Chomsky và dạng chuẩn Greibach. 3.2.1. Loại bỏ các ký tự thừa 1) Định nghĩa Một ký tự văn phạm X (X  V = NT) gọi là không thừa nếu tồn tại một dẫn xuất S * αXβ * w với các xâu α, β bất kỳ  V* và w  T*. Ngƣợc lại X gọi là thừa. Vậy, ký tự không thừa có 2 đặc điểm: - X là biến thì X phải dẫn ra một xâu các ký tự kết thúc; - X phải nằm trong dẫn xuất từ S. 2) Bổ đề 1 (Dùng loại bỏ các biến không dẫn ra xâu ký tự kết thúc) Cho CFG G = (N, T, P, S) với L(G) ≠ ∅, có một CFG G‟= (N‟, T, P‟, S) tƣơng đƣơng sao cho mỗi A  N‟ tồn tại w  T* để A * w. Chứng minh: Với mỗi biến A  N và với mỗi luật sinh A → w với w T* nằm trong P thì rõ ràng A N‟. Nếu A → X X ... X là một luật sinh, trong đó mỗi X hoặc là ký tự kết thúc 1 2 n i hoặc là một biến đã có sẵn trong N‟ thì một xâu các ký tự kết thúc có thể đƣợc dẫn ra từ A bằng dẫn xuất bắt đầu A  X X ... X , vì vậy A  N‟. 1 2 n Tập N‟ có thể tính đƣợc bằng cách lặp lại bƣớc trên cho đến khi không thêm đƣợc ký tự nào nữa vào N‟. P‟ là tập tất cả các luật sinh mà các ký tự của nó thuộc N‟  T. Giải thuật tìm N‟ nhƣ sau: Begin OLDN:= ∅; (1) NEWN:= {A  N | A → w  P và w  T*}; (2) While OLDN NEWN do (3) begin OLDN:= NEWN; (4) 118 Phạm Hùng Phú
  13. Câu hỏi và bài tập chƣơng 3 NEWN:= {A  N | A → α với α  (T  OLDN)*} (5) end; N‟:= NEWN; (6) end; Rõ ràng rằng nếu biến A đƣợc thêm vào N‟ tại bƣớc (2) hoặc (5) thì A sẽ dẫn ra đƣợc xâu ký tự kết thúc. Ta chứng minh rằng nếu A dẫn ra đƣợc một xâu ký tự kết thúc thì A đƣợc thêm vào tập NEWN. Dùng chứng minh quy nạp theo độ dài của dẫn xuất A * w. Nếu độ dài bằng 1 thì A → α là một luật sinh trong P. Vậy A đƣợc đƣa vào N‟ tại bƣớc (2). Giả sử kết quả đúng tới k -1 bƣớc dẫn xuất ( k >1) Nếu A  X X ... X * w bằng k bƣớc thì ta có thể viết w = w w ... w , 1 2 n 1 2 n trong đó X * w , với 1 ≤ i ≤ n bằng ít hơn k bƣớc dẫn xuất. Theo giả thiết quy nạp i i thì các biến X này đƣợc thêm vào N‟. Khi X cuối cùng đƣợc thêm vào N‟ thì vòng i i lặp (3) vẫn tiếp tục lặp một lần nữa và A sẽ đƣợc thêm vào N‟ tại (5). Ta chứng minh L(G‟) = L(G): Chọn N‟ là tập hợp tại (6) và P‟ là tập tất cả các luật sinh mà các ký tự của nó thuộc (N‟T) thì chắc chắn rằng có tồn tại văn phạm G‟= (N‟, T, P‟, S) thoả mãn tính chất: nếu A N‟ thì A * w với w nào đó thuộc T*. Hơn nữa, mỗi luật sinh của P‟ đều là luật sinh của P nên ta có L(G‟)  L(G). Ngƣợc lại giả sử một từ w  L(G) – L(G‟) thì một dẫn xuất bất kỳ của w phải liên quan đến các biến thuộc N – N‟ hoặc luật sinh thuộc P – P‟ (các dẫn xuất này đƣa ra các biến thuộc N – N‟), nhƣng do không có biến nào trong N – N‟ dẫn đến xâu các ký tự kết thúc, điều này dẫn đến mâu thuẫn. Vậy L(G‟) = L(G). Từ việc chứng minh bổ đề 1, ta có giải thuật sau. 3) Giải thuật loại bỏ biến không dẫn xuất ra xâu các ký tự kết thúc Input G = (N, T, P, S) - CFG Output G‟= (N‟, T‟, P‟, S‟) - CFG mà mọi biến của nó đều sinh ra xâu ký tự kết thúc và L(G‟) = L(G) Phạm Hùng Phú 119
  14. Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống Process Bước 1: khởi tạo S‟ = S; T‟ = T; N‟ = {A  N  A → w  P và w T*}; Bước 2: Xác định N‟ Với mỗi luật sinh A → X X ... X  P kiểm tra 1 2 n Nếu X  N‟ T‟ i thì N‟ = N‟{A}; i Bước 3: Quay lại bƣớc 2 cho đến khi gặp một lƣợt không thêm đƣợc biến nào vào N‟ nữa. Bước 4: xác định p’ P‟ ={ A → X X ... X  P  AN‟ và X (N‟ T‟)* i} 1 2 n i Ví dụ: Xét văn phạm G = (N, T, P, S): N = S, A, B, C, D T = a, b, c, d S = S; P: có các luật sinh sau: S → AB | a; A→a; C → b; D → bA. Áp dụng giải thuật trên, ta có: 1. G‟= (N‟, T‟, P‟, S‟): T‟ = a, b, c, d S‟ = S; 2. N‟: Bƣớc N‟ Giải thích KT {S, A, C} S → a; A → a; C → b 1 {S, A, C, D} D → bA; S → a; A → a; C → b 2 {S, A, C, D} D → bA; S → a; A → a; C → b 3. P‟ = {S → a; A → a; C → b; D → bA}. 4) Bổ đề 2 (Dùng loại bỏ các ký tự không nằm trong xâu đƣợc dẫn xuất ra từ ký tự bắt đầu văn phạm) 120 Phạm Hùng Phú
  15. Câu hỏi và bài tập chƣơng 3 Nếu G = (N, T, P, S) là CFG thì ta có thể tìm đƣợc CFG G‟ = (N‟, T‟, P‟, S) tƣơng đƣơng sao cho mỗi X  N‟  T‟ tồn tại α, β  (N‟  T‟)* để S * αXβ. Chứng minh: Tập N‟  T‟ gồm các ký tự xuất hiện trong dạng câu của G đƣợc xây dựng bởi giải thuật lặp nhƣ sau: Bước1: Đặt N‟ = {S}; T‟ = ∅; Bước2: Với mỗi A  N‟ thực hiện - Tìm tất cả các luật sinh A → α | α | ... | α là các luật sinh trong P 1 2 n - Nếu có thì thêm tất cả các biến của α , α , ... , α vào N‟ và các ký tự 1 2 n kết thúc của α , α ,..., α vào T‟. 1 2 n Bước3: Lặp lại bƣớc 2 cho đến khi không còn biến hoặc ký tự kết thúc nào đƣợc thêm vào nữa. Dễ thấy, X  N‟  T‟ thì tồn tại α, β  (N‟  T‟)* để S * αXβ, trong đó P‟ là tập hợp tất cả các luật sinh của P chỉ chứa các ký tự thuộc (N‟  T‟). Ta dễ dàng chứng minh L(G‟) = L(G) . Từ việc chứng minh bổ đề 2, ta có giải thuật sau. 5) Giải thuật loại bỏ ký hiệu không được dẫn xuất ra từ ký hiệu bắt đầu Input G = (N, T, P, S) - CFG Output G‟= (N‟, T‟, P‟, S‟) - CFG mà mọi ký hiệu của nó đều đƣợc dẫn xuất ra từ ký hiệu bắt đầu và L(G‟) = L(G) Process Bước1: Khởi tạo S‟ = S; N‟ = {S}; T‟ = ∅ Bước2: Xác định N‟, T‟ + Với mỗi A  N‟ thực hiện - Tìm tất cả các luật sinh A → α | α | ... | α là các luật sinh trong P 1 2 n - Nếu có thì thêm tất cả các biến của α , α , ... , α vào N‟ và các ký tự 1 2 n kết thúc của α , α ,..., α vào T‟ ; 1 2 n Phạm Hùng Phú 121
  16. Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống Bước3: Quay lại bƣớc 2 cho đến khi gặp một lƣợt không còn biến hoặc ký tự kết thúc nào đƣợc thêm vào N‟ và T‟ nữa. Bước 4: xác định p’ P‟ ={ A → X X ... X  P  AN‟ và X (N‟ T‟)* i} 1 2 n i Ví dụ 1: Loại bỏ ký tự không đƣợc dẫn xuất ra từ ký hiệu bắt đầu trong văn phạm sau: G = (N, T, P, S): N = S, A, B, C, D T = a, b, c, d S = S; P: có các luật sinh sau: S → AB | a; A → a; C → b; D → bA. Áp dụng giải thuật trên, ta có: 1. G‟= (N‟, T‟, P‟, S‟): S‟ = S; 2. N‟, T‟: Bƣớc N‟ T‟ Giải thích KT {S}   1 {S, A, B} {a} S → AB a 2 {S, A, B} {a} A→a 3. P‟= {S → AB a; A → a}. Ví dụ2: Loại bỏ các ký thừa trong văn phạm trên - Theo ví dụ trên loại bỏ ký tự không đƣợc sinh ra từ ký hiệu bắt đầu ta có văn phạm với tập luật sinh: S → AB  a; A → a. - Áp dụng giải thuật loại bỏ các biến không sinh ra ký tự kết thúc, ta thu đƣợc văn phạm với tập luật sinh: S → a Nhƣ vậy, để loại bỏ các ký thừa trong văn phạm phi ngữ cảnh, ta chỉ việc thực hiện hai công việc: Loại bỏ các biến không sinh ra ký tự kết thúc và các ký tự không đƣợc dẫn xuất ra từ ký hiệu bắt đầu. Từ đó ta có định lý. 122 Phạm Hùng Phú
  17. Câu hỏi và bài tập chƣơng 3 6) Định lý Mỗi ngôn ngữ phi ngữ cảnh (CFL) không rỗng đƣợc sinh ra từ một văn phạm phi ngữ cảnh (CFG) không có ký tự thừa. Chứng minh: Đặt L = L(G) là CFL không rỗng. Đặt G là kết quả của việc áp dụng bổ đề 1 vào G và G là kết quả của việc áp 1 2 dụng bổ đề 2 vào G . 1 Giả sử G có ký tự thừa là X. Theo bổ đề 2 ta có S * αXβ. Vì tất cả các ký tự 2 G2 trong G đều có trong G nên theo bổ đề 1: S * αXβ * w với w là xâu ký tự kết 2 1 G1 G1 thúc. Vì vậy không có ký tự nào trong dẫn xuất αXβ * w bị loại bỏ bởi bổ đề 2, vậy X G1 dẫn ra ký tự kết thúc trong G . Suy ra X là ký tự không thừa (mâu thuẫn). 2 Vậy văn phạm G không có ký tự thừa nào. 2 Ví dụ: Cho văn phạm G = (N, T, P, S): N = S, , , C, D T = a, b, c S = S; P: S  a;   a; S  b;   b; D  c; A  BC; Hãy loại bỏ các ký tự thừa trong văn phạm trên. - Áp dụng giải thuật loại bỏ các biến không sinh ra ký tự kết thúc: 1. G‟= (N‟, T‟, P‟, S‟): T‟ = a, b, c S‟ = S; 2. N‟: Bƣớc N‟ Giải thích KT {A, B, D} B → a; A → b; D → c 1 {S, B, D, A} S  a; S  b; B → a; A → b; D → c 2 {S, A, B, D} S  a; S  b; B → a; A → b; D → c Phạm Hùng Phú 123
  18. Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống 3. P‟= {S →Aa; S → Bb; B → a; A → b; D → c }. - Áp dụng giải thuật loại bỏ các ký tự không đƣợc dẫn xuất ra từ ký hiệu bắt đầu: 1. G” = (N”, T”, P”, S”): S” = S; 2. N” và T”: Bƣớc N” T” Giải thích KT {S}  1 {S , A, B} {a, b} S  a; S  b 2 {S, A, B} {a, b} S  a; S  b; A → b;   a 3. P” = {S → Aa; S → Bb; A → b; B → a}. Khi đó L(G) = L(G”) và G” không chứa ký hiệu thừa. 3.2.2. Luật sinh ε (ε quy tắc) 1) Định nghĩa - Một luật sinh có dạng A → ε đƣợc gọi là luật sinh ε (ε quy tắc). - Một biến A đƣợc gọi là biến rỗng (nullable) nếu A + ε Ta xét đến việc loại bỏ các luật sinh ε. Nếu ε  L(G) thì không thể loại đƣợc tất cả các luật sinh ε, nhƣng nếu ε ∉ L(G) thì có thể. Phƣơng pháp loại bỏ dựa trên việc xác định liệu một biến A có là biến rỗng hay không ?. Ta có thể thay thế mỗi luật sinh B → X X ... X bằng tất cả các luật sinh đƣợc định dạng bởi việc xóa bỏ 1 2 n tập hợp con các biến X rỗng, nhƣng không bao gồm luật sinh B → ε, ngay cả khi tất i cả các X đều là biến rỗng. i 2) Bổ đề 3 (Dùng để loại bỏ luật sinh ε) Cho CFG G = (N, T, P, S) với ε L(G), có một CFG G‟= (N‟, T, P‟, S) tƣơng đƣơng sao cho G‟ không chứa luật sinh ε. Chứng minh: Ta có thể xác định tập hợp các biến rỗng (nullable) của G bằng giải thuật lặp nhƣ sau: - Bắt đầu, nếu A → ε là một luật sinh thì A là biến rỗng. 124 Phạm Hùng Phú
  19. Câu hỏi và bài tập chƣơng 3 - Kế tiếp, nếu B → α, trong đó α gồm toàn các ký tự là các biến rỗng đã đƣợc tìm thấy trƣớc đó thì B cũng là biến rỗng. - Lặp lại cho đến khi không còn biến rỗng nào đƣợc tìm thấy nữa. Tập luật sinh P‟ đƣợc xây dựng nhƣ sau: Nếu A → X X ... X là một luật sinh trong 1 2 n P thì ta thêm tất cả các luật sinh A → α α ... α vào P‟ với điều kiện: 1 2 n 1. Nếu X không là biến rỗng thì α = X ; i i i 2. Nếu X là biến rỗng thì α là X hoặc ε; i i i 3. Không phải tất cả α đều bằng ε. i Đặt G‟ = (N, T, P‟, S). Ta sẽ chứng minh rằng với mọi A  N và w T*; A * ‟ w nếu và chỉ nếu w ≠ ε và A * w. G G - Thuận: i Đặt A  w và w ≠ ε, ta chứng minh quy nạp rằng A * ‟‟ w. G G Nếu i = 1 ta có A → w là một luật sinh trong P, và vì w ≠ ε nên luật sinh này cũng thuộc P‟. Giả sử kết quả đúng tới i - 1 (i >1) i -1 Xét A  X X ...X  w. Ta viết w = w w ...w sao cho với j, X * w . G 1 2 n G 1 2 n j j Nếu w ≠ ε và X là biến thì theo giả thiết quy nạp, ta có X  ‟‟ w (vì dẫn * j j j G j xuất X * w có ít hơn i bƣớc). Nếu w = ε thì X là biến rỗng, vậy A → β β ...β là j j j j 1 2 n một luật sinh trong P‟, trong đó β = X nếu w ≠ ε và β = ε nếu w = ε. j j j j j Vì w ≠ ε nên không phải tất cả β là ε. Vậy, ta có dẫn xuất: j A  β β ...β * w β ...β * w w β ...β * ... * w w ...w = w trong G‟‟. 1 2 n 1 2 n 1 2 3 n 1 2 n - Đảo: i Giả sử A  ‟ w. Chắc chắn rằng w ≠ ε vì G‟ không có luật sinh ε. Ta quy G nạp theo i rằng A * w. G Nếu i = 1: Ta thấy A → w là một luật sinh trong P‟, do đó cũng phải có luật sinh A → w trong P sao cho bằng việc loại bỏ các ký tự rỗng trong α, ta có w. Vậy, Phạm Hùng Phú 125
  20. Chương 3. Văn phạm phi ngữ cảnh và Automat đẩy xuống có tồn tại dẫn xuất A  α * w, trong đó α * w liên quan đến các dẫn xuất ε từ G G các biến rỗng của α mà chúng ta đã loại bỏ khỏi w. Giả sử kết quả đúng tới i - 1 (i >1) i-1 Xét A  ‟ X X ... X  ‟ w. Phải có luật sinh A → β trong P sao cho G 1 2 n G X X ... X tìm đƣợc khi loại bỏ các biến rỗng của β. Vậy A * X X ...X (chứng 1 2 n G 1 2 n minh tƣơng tự nhƣ ở trên). Ta viết w = w w ...w sao cho với j ta có X * ‟ w 1 2 n j G j (bằng ít hơn i bƣớc). Theo giả thiết quy nạp X * ‟ w nếu X là biến. Nếu X là ký j G j j j tự kết thúc thì w = X và X * w là hiển nhiên. Vậy A * w. j j j G j G Hơn nữa S  w nếu và chỉ nếu S  w. Vậy L(G‟) = L(G) - {ε}. * * G‟ G Từ việc chứng minh bổ đề trên, ta có giải thuật sau. 3) Giải thuật loại bỏ luật sinh  Input G = (N, T, P, S) – CFG, L(G) Output G‟= (N‟, T‟, P‟, S‟) – CFG, G‟ không chứa luật sinh  và L(G‟) = L(G) Process Bước1: Khởi tạo N‟ = N; T‟ = T; S‟ = S; P‟ = ; R = {AN‟  A →   P} Bước2: Tìm Tập các biến rỗng R Với mỗi luật sinh A → X X ... X  P kiểm tra 1 2 n Nếu X  R i thì R = R{A}; i Bước3: Quay lại bƣớc 2 cho đến khi không còn biến rỗng nào đƣợc thêm vào R nữa. Bước4: Xác định P‟ Với mỗi luật sinh A → X X ... X P không là luật sinh ε thực hiện 1 2 n Thêm tất cả các luật sinh A → α α ... α vào P‟ với điều kiện: 1 2 n 1. Nếu X không là biến rỗng thì α = X ; i i i 2. Nếu X là biến rỗng thì α là X hoặc ε; i i i 126 Phạm Hùng Phú
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2