0.5 Văn phạm chính quy và các tính chất  (Page 2/5)

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 G1 ({S}, {a, b}, P1, 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 G2 ({S, A, B}, {a, b}, P2, 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.