構造一個CFG for

我嘗試：

S = SA|e 

A = aAB|e 

B = bB|e

我沒有辦法證實我的答案，這是正確的？

來源

2012-02-23 Nitin

這是不正確的，因爲沒有辦法得到一個單一的「B」（或任何數量的「B」沒有任何「A」）。

（我想你可以通過改變只有一個字母解決它; O）

PS對不起，前面不正確答覆;認爲這是爲我= j。

來源

2012-02-23 03:02:41

所以它正確的我！= j？另外，您是否還可以快速確認L2 = {a^2n b^n，n> = 0}是{S = ASB | e} {A = A | aa | e} {B = b | e}？堆棧讓我發表另一個問題'因爲我是一個新手！ – Nitin 2012-02-23 03:17:21

不，這是不正確的，我！= j - 看到參數。它不能產生「b」。我的「對不起」是關於我刪除的更早的答案（我擔心你可能在我刪除之前閱讀過）。你的L2也是不正確的 - 它可能更簡單（根本不需要A和B）。例如，L2可以給出S→ASB→aaSB→aaB→aa。 – 2012-02-23 03:20:30

好的抱歉在這種情況下誤讀你的遺憾。感謝我現在拿到L1。但是對於L2來說，我的回答是不正確的，因爲它必須是最簡單的形式，還是不能正確生成？ – Nitin 2012-02-23 03:44:58

您定義了L1 = {a^i b^j | i，j> = 0}。換言之，這是所有字符串的語言，它們以零個或多個a開始，以零個或多個b結尾。這是一種常用語言;它的正則表達式是a * b *。正規文法（也有上下文無關文法）如下：

S := lambda | aS | bT 
T := lambda | bT

另一個上下文無關文法如下：

S := lambda | aS | Sb

很抱歉，如果我失去了一些東西，你的語言更比我正在閱讀的還要複雜。如果您有理由相信所定義的L1與我描述的語言不同，請解釋。

來源

2012-02-23 03:24:53 Patrick87

謝謝！我知道我的答案是沒有產生任何b的產品。我試着再次解決它，得到了{S：= lambda | ASB} {A：= lambda | a} {B：= lambda | b}但它仍然不同於您的解決方案，但僅僅是因爲您的是一個簡化版本還是我在第二次嘗試時弄錯了？這並不複雜，它確實很簡單。我正在學習它新鮮。 – Nitin 2012-02-23 03:48:46

你好，Nitin（這不簡單，但它的工作原理）。 – 2012-02-23 04:34:29

構造一個CFG for

回答

相關問題