0.1 Ôtômát tuyến tính giới nội và văn phạm cảm ngữ cảnh  (Page 3/4)

Thí dụ 8.2 : Xét CSG G (V, T, P, S) với các luật sinh được cho như trong Thí dụ 8.1 trên và xét chuỗi nhập w = abbc. Ta cần xác định xem liệu chuỗi w  L(G)?

Để tìm đường đi từ đỉnh S tới đỉnh abbc trong đồ thị nói trên ta có thể dùng phương pháp “vết dầu loang” như sau:

Lập các R(i), i = 0, 1, 2, … theo quy tắc sau:

R(0) = { S }

R(i) = R(i -1)  {      với   R(i -1) và      w  }

Do R(0)  R(1)  …  R(i)  R(i +1)  …  tập các đỉnh, vậy tồn tại số k nào đó sao cho:

R(k) = R(k +1) = R(k +2) = …

Do đó quá trình thành lập các R(i) sẽ có thể ngừng sau k bước.

Và w  L(G) khi và chỉ khi có i  k để cho w  R(i).

Trong thí dụ trên, giả sử khi ta xét  w = 4, ta có:

R(0) = { S }

R(1) = {S, aSBC, aBC}

R(2) = {S, aSBC, aBC, abC}

R(3) = {S, aSBC, aBC, abC, abc}

R(4) = R(3)

Vậy chuỗi abbc không thuộc L(G).

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, , ,,qo,, $, 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: