Hỏi về code loại bỏ ký hiệu vô sinh trong văn phạm phi ngữ cảnh?

[Le_Vi (Lê Vi)]

Đề bài:Viết chương trình loại bỏ ký hiệu vô sinh ?
input: văn phạm phi ngữ cảnh có ký hiệu vô sinh
output: văn phạm phi ngữ cảnh không còn ký hiệu vô sinh
Mong mọi người giúp em!

[SITUVN.gcd]

“Kí hiệu vô sinh”. Đề nghị giải thích ý nghĩa.

[qloved (Quân)]

kí hiệu vô sinh là gì vậy bạn. Google dịch ra hay sao ấy nhỉ

[rogp10]

https://www.sanfoundry.com/automata-theory-cfg-eliminating-useless-symbols/ ?

Useless symbols có 2 loại:

• Như vòng lặp vô tận
• Ko thể dẫn xuất ra được

[Le_Vi (Lê Vi)]

Là kí hiệu mà từ nó không dẫn ra chuỗi ký hiệu kết thúc cũng như không được dẫn ra từ kí hiệu bắt đầu văn phạm.

[Reborn (David Martin)]

Cho mình xin mẫu 1 sentence có ký hiệu này xem nào, nhớ bôi đỏ nó lên nhé.
Nếu đề là English bạn cứ post nguyên văn, nhiều lúc bạn giải thích tiếng Việt nó còn tối nghĩa hơn ấy.

[Le_Vi (Lê Vi)]

Xét văn phạm có các luật sinh sau:
S \rightarrow AB \: | \: a \: | \: b
A \rightarrow a

Áp dụng bổ đề 1, ta thấy không có ký hiệu kết thúc được nào dẫn ra từ B nên ta loại bỏ B và luật sinh S \rightarrow AB. Tiếp tục, áp dụng bổ đề 2 cho văn phạm:
S \rightarrow a \: | \: b
A \rightarrow a

Ta thấy chỉ có S xuất hiện trong dạng câu. Vậy ({S}, {a}, {S \rightarrow a}, S) là văn phạm tương đương với văn phạm đã cho và không có ký hiệu vô ích.

BỔ ĐỀ 1: (Dùng loại bỏ các biến không dẫn ra chuỗi ký hiệu kết thúc)
Cho CFG G (V, T, P, S) với L(G) \neq \emptyset, có một CFG G’ (V’, T’, P’, S) tương đương sao cho mỗi A \in V’ tồn tại w \in T^* để A \Rightarrow^* w.

Chứng minh:
Mỗi biến A với luật sinh A \rightarrow w trong P thì rõ ràng A \in V’. Nếu A \rightarrow X_1X_2 \dots X_n là một luật sinh, trong đó mỗi X_i hoặc là ký hiệu kết thúc hoặc là một biến đã có sẵn trong V’ thì một chuỗi các ký hiệu kết thúc có thể được dẫn ra từ A bằng dẫn xuất bắt đầu A.

\Rightarrow X_1X_2 \dots X_n, vì vậy A \in V’. Tập V’ có thể tính được bằng cách lặp lại giải thuật trên.
P’ là tập tất cả các luật sinh mà các ký hiệu của nó thuộc V’ \cup T.
Giải thuật tìm V’ như sau:

Begin
(1) OLDV := \emptyset ;
(2) NEWV:= \{A \: |\: A \rightarrow w \textrm{ với } w \in T^* \};
(3) While OLDV \neq NEWV do
begin
(4) OLDV:= NEWV;
(5) NEWV:= OLDV \cup \{ A \: | \: A \rightarrow \alpha \textrm{ với } \alpha \in (T \cup OLDV)^* \}
end;
(6) V’:= NEWV;
end;

Rõ ràng rằng nếu biến A được thêm vào V’ tại bước (2) hoặc (5) thì A sẽ dẫn ra được chuỗi ký hiệu kết thúc. Ta chứng minh rằng nếu A dẫn ra được một chuỗi ký hiệu kết thúc thì A được thêm vào tập NEWV.

Dùng chứng minh quy nạp theo độ dài của dẫn xuất A \Rightarrow^* w.
Nếu độ dài bằng 1 thì A \rightarrow \alpha là một luật sinh trong P. Vậy A được đưa vào V’ 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 \Rightarrow X_1X_2 \dots X_n \Rightarrow^* w bằng k bước thì ta có thể viết w = w_1w_2 \dots w_n, \textrm{ trong đó } X_i \Rightarrow^* w_i, với 1 \le i \le n bằng ít hơn k bước dẫn xuất. Theo giả thiết quy nạp thì các biến X_i này được thêm vào V’. Khi X_i cuối cùng được thêm vào V’ thì vòng 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 V’ tại (5).

Ta chứng minh L(G’) = L(G)
Chọn V’ 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ý hiệu của nó
thuộc (V’ \cup T) thì chắc chắn rằng có tồn tại văn phạm G’ (V’, T, P’, S) thoả mãn tính chất: nếu A \in V’ thì A \Rightarrow^* 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’) \subset L(G).

Ngược lại giả sử một từ w \in 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 V – V’ 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 V – V’), nhưng do không có biến nào trong V – V’ dẫn đến chuỗi kết
thúc, điều này dẫn đến mâu thuẫn. Vậy L(G’) = L(G).

Hay có thể nói 2 ngôn ngữ được cho từ 2 văn phạm G và G’ là tương đương nhau, hay nói cách khác: nếu có một văn phạm G thì luôn luôn có một văn phạm G’ tương ứng mà trong đó mỗi biến của G’ đều cho ra ký hiệu kết thúc.

BỔ ĐỀ 2: (Dùng loại bỏ các biến không được dẫn ra từ ký hiệu bắt đầu văn phạm)
Nếu G (V, T, P, S) là CFG thì ta có thể tìm được CFG G’ (V’, T’, P’, S) tương
đương sao cho mỗi X \in V’ \cup T’ tồn tại \alpha, \beta \in (V’ \cup T’)^* để S \Rightarrow^* \alpha X \beta.

Chứng minh:
Tập V’ \cup T’ gồm các ký hiệu 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:

• Đặt V’ = {S}; T’ = \emptyset;
• Nếu A \in V’ và A \rightarrow \alpha_1 \: | \: \alpha_2 \: | \dots | \: \alpha_n là các luật sinh trong P thì thêm tất cả các biến của \alpha_1, \alpha_2, \dots , \alpha_n vào V’ và các ký hiệu kết thúc của \alpha_1, \alpha_2, \dots, \alpha_n vào T’.
• Lặp lại giải thuật cho đến khi không còn biến hoặc ký hiệu kết thúc nào được
  thêm vào nữa.

Dễ thấy, X \in V’ \cup T’ thì tồn tại \alpha, \beta \in (V’ \cup T’)^* để S \Rightarrow^* \alpha X \beta, trong đó P’ là tập hợp tất cả các luật sinh của P chỉ chứa các ký hiệu thuộc (V’ \cup T’).
Ta dễ dàng chứng minh L(G’) = L(G) .