爲語法指定語言

是否有任何特定的方法遵循指定給定語法的語言？即是否有必要運行語法中給出的所有生產規則來確定它所代表的語言？因爲我正在從事的是家庭作業問題，所以我沒有這樣的例子。爲語法指定語言

[edit]: adding an example, Describe, in English, the language defined by the grammar 

    <S> -> <A> <B> <C> 
     <A> -> a <A> | a 
     <B> -> b <B> | b 
     <C> -> c <C> | c

問候，

darkie15

來源

2010-05-29 name_masked

定義「指定」的含義。通常，語法本身被認爲是該語言的規範。 – 2010-05-29 10:22:57

您可能想查閱[Tree Automata Techniques and Applications]（http://tata.gforge.inria.fr/）書，特別是第1章和第2.4章。下載是免費的，從理論的角度來看，它提供了一個很好的方法。 – tonio 2010-05-29 11:05:18

「猜測」語法定義的語言，然後使用歸納法向自己（或您的教授）證明您的猜測是正確的。 – 2010-05-29 11:33:31

在您例如，部分

<A> -> <A> a | a

承認a 這同樣適用於其他兩個作品，<B>，準確地非空列表<C>，分別爲b和c。

因此，<S> -> <A> <B> <C>，你推斷，這個語法識別的語言是a任何非空列表，後面的b一個非空列表，那麼c一個非空列表，對應於正則表達式a+b+c+。

證明從這裏很容易證明，由正則表達式識別的每個實例都被語法識別，使用歸納法。

來源

2010-05-29 16:11:10 tonio

爲語法指定語言

回答

相關問題