資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 CFG 構建一對語言
問題
考慮以下上下文無關文法 (CFG)，找出 G1 和 G2 分別可以生成的語言對。
解決方案
考慮以下 CFG −
G1 : S->aS|B , B->b l bB
G2: S->aA | bB , A->aA| B | ε , B->bB | ε
現在，我們可以按以下步驟生成語言。首先考慮 G1，如下所示
Consider G1: S->aS|B B->b|bB Using S->B ->b b can be generated Using S->B ->bB ->bb bb can be generated Using S->aS ->aB ->ab ab can be generated Using S->aS ->aB ->abB ->abb abb can be generated
可以看到，a 的個數可以為 0 也可能大於 0，但是 b 的個數總大於 0。
因此，結果將如下所示 −
L(G1)= {ambn | m>=0 & n>0 }現在，考慮 G2，如下所示 −
Consider G2: S->aA|bB A->aA|B| ε B->bB| ε Using S->aA ->a a can be generated Using S->bB ->b b can be generated Using S->aA ->aaA ->aa aa can be generated Using S->bB ->bbB ->bb bb can be generated Using S->aA ->aB ->abB ->abb abb can be generated
可以看到，a 和 b 中必須有一個大於 0。
因此，結果將如下所示 −
L(G2)= {aman |m>0 or n>0}
更新於: 2021 年 6 月 12 日
200 次瀏覽
廣告