Văn phạm chính quy (rg : REGULAR GRAMMAR)

Tài liệu tham khảo :

V.J. Rayward-Smith – A First course in Formal Language Theory (Second Editor) – McGraw-Hill Book Company Europe – 1995 (Chapter 3 : Regular Language I )

Hồ Văn Quân – Giáo trình lý thuyết ôtômát và ngôn ngữ hình thức – Nhà xuất bản Đại học quốc gia Tp. Hồ Chí Minh – 2002 (Chương 4 : Văn phạm chính quy)

From Wikipedia, the free encyclopedia - Regular Grammar:

http://en.wikipedia.org/wiki/Regular_grammar

Văn phạm tuyến tính

Một văn phạm G(V, T, P, S) được gọi là tuyến tính trái (left - linear) nếu tất cả các luật sinh của nó có dạng :

A → Bw

A → w

trong đó A, B là các biến ∈ V; w là một chuỗi các ký hiệu kết thúc ∈ T^* (có thể rỗng).

Một văn phạm G(V, T, P, S) được gọi là tuyến tính phải (right - linear) nếu tất cả các luật sinh của nó có dạng :

A → wB

A → w

Một văn phạm được gọi là văn phạm chính quy nếu nó thuộc dạng văn phạm tuyến tính trái hoặc tuyến tính phải.

Thí dụ 4.1 : Văn phạm sinh ra các số nguyên không dấu như đã nêu ở trên là văn phạm chính quy vì các luật sinh của nó có dạng tuyến tính phải.

Thí dụ 4.2 : Các văn phạm sau đây là văn phạm chính quy :

Văn phạm G₁ ({S}, {a, b}, P₁, S) với các luật sinh được cho như sau :

S → abS | a

là văn phạm tuyến tính phải.

Văn phạm G₂ ({S, A, B}, {a, b}, P₂, S) với các luật sinh được cho như sau : S → Aab

A → Aab | B

B → a

là văn phạm tuyến tính trái.

Thí dụ 4.3 : Ngôn ngữ được ký hiệu bởi biểu thức chính quy 0(10)* được sinh bởi văn phạm tuyến tính phải có các luật sinh sau :

S → 0A (1)

A → 10A | ε

Và bởi văn phạm tuyến tính trái :

S → S10 | 0 (2)

Sự tương đương giữa văn phạm chính quy và ôtômát hữu hạn

Văn phạm chính quy mô tả tập hợp chính quy trong ngữ cảnh một ngôn ngữ là chính quy khi và chỉ khi nó được sinh ra từ văn phạm tuyến tính trái hoặc văn phạm tuyến tính phải. Kết quả này được xác định bởi hai định lý sau :

ĐỊNH LÝ 4.1 : Nếu L được sinh ra từ một văn phạm chính quy thì L là tập hợp chính quy.

Chứng minh

Trước hết, ta giả sử L = L(G) với một văn phạm tuyến tính phải G(V, T, P, S). Ta xây dựng một NFA có chứa ε-dịch chuyển M (Q, T, δ, [S], [ε]) mô phỏng các dẫn xuất trong G.

Q bao gồm các trạng thái có dạng [α] với α là S hoặc chuỗi hậu tố của vế phải một luật sinh nào đó trong P.

Ta định nghĩa δ như sau :

1. Nếu A là một biến, thì δ([A], ε) = {[α] | A → α là một luật sinh}
2. Nếu a thuộc T và α thuộc T^*  T^*V, thì δ([aα], a) = {[α]}

Sau đó, ta có thể dễ dàng chứng minh quy nạp theo độ dài của dẫn xuất rằng δ ([S], w ) chứa [ α ] khi và chỉ khi có chuỗi dẫn xuất S ⇒ * xA ⇒ xy α với A → y α là một luật sinh trong P và xy = w, hay nếu α = S thì w = ε . Khi [ ε ] là trạng thái kết thúc duy nhất, M chấp nhận w khi và chỉ khi S ⇒ * xA ⇒ w. Nhưng vì mọi chuỗi dẫn xuất cho một chuỗi ký hiệu kết thúc qua ít nhất 1 bước, nên ta thấy rằng M chấp nhận w khi và chỉ khi G sinh ra w. Vì vậy, mọi văn phạm tuyến tính phải đều sinh ra một tập hợp chính quy.

Bây giờ, giả sử G(V, T, P, S) là một văn phạm tuyến tính trái. Đặt văn phạm G’(V, T, P’, S) với P’ chứa các luật sinh của P có vế phải đảo ngược, nghĩa là :

P’ = { A → α | A → α^R ∈ P }

Nếu ta đảo ngược chuỗi vế phải các luật sinh trong một văn phạm tuyến tính trái, ta có văn phạm tuyến tính phải, và ngược lại. Do đó, hiển nhiên chúng ta có G’ là một văn phạm tuyến tính phải, và cũng dễ dàng để chỉ ra rằng L(G’) = L(G)^R. Theo chứng minh trên, ta có L(G’) là một tập chính quy. Mà thông thường một tập chính quy cũng vẫn còn giữ nguyên tính chất khi áp dụng phép đảo ngược nên L(G’)^R = L(G) cũng là một tập chính quy.

Vậy, mọi văn phạm tuyến tính trái hay phải đều sinh ra một tập hợp chính quy.

Thí dụ 4.3 : NFA được xây dựng từ Định lý 4.1 cho văn phạm tuyến tính phải (1) ở thí dụ 4.2 có dạng như hình 4.1 sau :

Xét văn phạm tuyến tính trái (2) ở thí dụ 4.2, nếu đảo ngược các vế phải luật sinh, ta có:

Hình 4.1 - NFA chấp nhận ngôn ngữ 0(10) *

Áp dụng các bước xây dựng NFA cho văn phạm này theo Định lý 4.1, ta có sơ đồ chuyển như Hình 4.2 (a). Nếu chúng ta đảo ngược các cạnh của NFA này và chuyển đổi vị trí các trạng thái bắt đầu và kết thúc, chúng ta sẽ có một NFA khác chấp nhận ngôn ngữ 0(10)*

Hình 4.2 - Xây dựng NFA cho 0(10) * từ văn phạm tuyến tính trái

ĐỊNH LÝ 4.2 : Nếu L là một tập hợp chính quy, thì L được sinh từ một văn phạm tuyến tính trái hoặc một văn phạm tuyến tính phải nào đó.

Chứng minh

Đặt L = L(M) với DFA M(Q, Σ, δ, q₀, F).

Trước hết, ta giả sử rằng trạng thái q₀ không phải là trạng thái kết thúc. Kế tiếp, ta đặt L = L(G) với văn phạm tuyến tính phải G(V, Σ, P, q₀), trong đó P chứa các luật sinh dạng p → aq nếu δ(p, a) = q và luật sinh dạng p → a nếu δ(p, a) là một trạng thái kết thúc. Rõ ràng δ(p, w) = q khi và chỉ khi có chuỗi dẫn xuất p ⇒*wq. Nếu wa được chấp nhận bởi M, ta đặt δ(q₀, w) = p, suy ra dẫn xuất q₀⇒*wq. Tương tự, nếu δ(p, a) là trạng thái kết thúc, vì p → a là một luật sinh, nên q₀⇒*wa. Ngược lại, đặt q₀⇒*x. Ta có x = wa và q₀⇒*wq ⇒wa với mọi p. Và vì δ(q₀, w) = p và δ(p, a) là trạng thái kết thúc nên do đó x ∈ L(M). Hay nói cách khác : L(M) = L(G) = L.

Bây giờ, xét q₀∈ F, vì thế chuỗi rỗng ε thuộc L. Lưu ý rằng văn phạm G vừa định nghĩa ở trên chỉ sinh ra ngôn ngữ L – {ε}. Chúng ta có thể sửa đổi G bằng cách thêm vào một ký hiệu bắt đầu S mới với luật sinh S → q₀ | ε. Văn phạm thu được vẫn có dạng tuyến tính phải và phát sinh ngôn ngữ L.

Để phát sinh một văn phạm tuyến tính trái cho L, ta bắt đầu với một NFA cho L^R và sau đó đảo ngược chuỗi vế phải cho tất cả mọi luật sinh của văn phạm tuyến tính phải vừa thu được.

Thí dụ 4.4 : Trong Hình 4.3 ta thấy sơ đồ chuyển DFA cho 0(10)*

Văn phạm tuyến tính phải sinh từ DFA này có dạng :

A → 0B|1D|0

B → 0D|1C

C → 0B|1D|0

D → 0D|1D

Trong văn phạm trên, biến D không có ích nên ta có thể loại bỏ D và tất cả các luật sinh liên quan tới D, rút gọn văn phạm thành :

A → 0B|0

B → 1C

C → 0B|0

Hình 4.3 - DFA cho 0(10) *