SỰ TƯƠNG ĐƯƠNG GIỮA LBA VÀ CSG
Chúng ta chú ý rằng LBA có thể chấp nhận các chuỗi rỗng ε, còn CSG không thể sinh ra chuỗi rỗng. Ngoài trường hợp đó ra thì LBA sẽ chấp nhận chính xác tất cả các chuỗi được sinh ra từ CSG.
ĐỊNH LÝ 8.2 : Nếu L là một CSG thì L sẽ được chấp nhận bởi một LBA nào đó.
Chứng minh
Cách chứng minh định lý này cũng tương tự như cách chứng minh của định lý 7.9 ở chương trước về sự tương đương giữa lớp ngôn ngữ sinh từ văn phạm loại 0 với lớp ngôn ngữ mà máy Turing chấp nhận, chỉ khác là ở đây không cần dùng một băng nhập thứ hai để phát sinh các dạng câu theo chuỗi dẫn xuất lần lượt theo các suy dẫn của văn phạm, mà chỉ cần dùng rãnh thứ hai trên băng nhập của LBA vào việc đó.
Cho G = (V, T, P, S) là một CSG, ta xây dựng ôtômát LBA M như sau: Băng nhập của LBA gồm hai rãnh : rãnh 1 chứa chuỗi nhập w với các ký hiệu đánh dấu , $ ở hai đầu, rãnh 2 dùng để phát sinh các dạng câu α. Trạng thái bắt đầu, nếu w = ε thì M ngừng và không chấp nhận input, nếu không thì đầu đọc viết ký hiệu S ở rãnh 2, ngay dưới ký hiệu bên trái nhất của chuỗi w, tiếp đó M thực hiện quá trình sau:
1) Chọn trong số không đơn định một chuỗi con β của chuỗi α trên rãnh 2 sao cho β → là một luật sinh trong P.
2) Thay β bởi , nếu cần thiết ta phải dịch chuyển phần cuối chuỗi sang phải cho đủ chỗ, tuy nhiên nếu dịch chuyển ra ngoài $ thì LBA ngừng và không chấp nhận.
3) (Hình thái hiện tại ở rãnh 1 là w $, còn ở rãnh 2 là chuỗi α, mà S ⇒G α và | α | ≤ | w |). So sánh rãnh 1 và rãnh 2, nếu α = w thì LBA ngừng và chấp nhận w. Nếu không thì trở về bước (1).
Như vậy khi M chấp nhận chuỗi w, thì S ⇒G* w. Ngược lại nếu S ⇒G* w thì mọi dạng câu α xuất hiện trong chuỗi dẫn xuất đó đều thoả mãn | α | ≤ | w |, bởi vì mọi luật sinh β → trong văn phạm G đều thỏa | β | ≤ | |. Như vậy M có thể thực hiện chuỗi dẫn xuất đó trên rãnh 2, giữa hai ký hiệu đánh dấu đầu mút và $. Vậy M chấp nhận chuỗi nhập w.
Tóm lại M sẽ chấp nhận mọi chuỗi sinh ra bởi văn phạm G.
ĐỊNH LÝ 8.3 : Nếu L = L(M) với một LBA M (Q, Σ , Γ , δ ,q o , , $, F) thì L – { ε } là một ngôn ngữ cảm ngữ cảnh.
Chứng minh
Cách chứng minh định lý này cũng tương tự như cách chứng minh của định lý 7.10 ở chương trước, bằng cách ta xây dựng một CSG G thực hiện 3 giai đoạn:
- Giai đoạn 1: Văn phạm cho phép sinh ra một chuỗi w (chuỗi nhập của M), cũng được chứa trong , $ và q0.
- Giai đoạn 2: Văn phạm lặp lại công việc của M.
- Giai đoạn 3: Khi xuất hiện trạng thái q ∈ F, ta thu về chuỗi w với lưu ý rằng các luật sinh α → β đều có | α | = | β |.
Quá trình mô phỏng lại các luật sinh đó bởi các luật sinh của CSG sẽ không có gì vướng mắc. Chỉ ở giai đoạn 3, việc xoá đi các ký hiệu đánh dấu hai đầu mút và $, q không được phép làm rút ngắn chuỗi nhập lại. Để giải quyết vướng mắc này, ta gắn các ký hiệu , $, q kề bên với các ký hiệu của chuỗi nhập mà không để đứng rời ra như trước.
Cụ thể, giai đoạn 1 thực hiện bởi các luật sinh trong G sau:
S1 → [a, q0 a]S2 S1 → [a, q0a$]
S2 → [a, a]S2, S2 → [a,a$]
∀a ∈ Σ - {, $}
Các luật sinh trong G cho phép thực hiện giai đoạn 2, giống như LBA M thực hiện (sinh viên tự xây dựng xem như bài tập).
Cuối cùng, ở giai đoạn 3, các luật sinh sau đây sẽ được sử dụng, với q ∈ F :
[a, αqβ] → a
∀a ∈ Σ - {, $} và ∀α, β có thể có.
Chú ý rằng số luật sinh là hữu hạn, vì α và / hoặc β chỉ gồm , $ và một ký hiệu nhập vào. Chúng ta cũng có thể xoá thành phần thứ hai của một biến nếu nó liền kề với ký hiệu kết thúc bằng cách dùng các luật sinh dạng:
[a, α]b → ab
b[a, α] → ba
∀a, b ∈ Σ - {, $} và ∀α có thể có.
Như vậy các luật sinh vừa được xây dựng mô tả văn phạm là CSG và có thể chứng minh L(M) - {ε} = L(G).