为语法指定语言

问题描述：

是否有任何特定的方法遵循指定给定语法的语言？即是否有必要运行语法中给出的所有生产规则来确定它所代表的语言？因为我正在从事的是家庭作业问题，所以我没有这样的例子。为语法指定语言

[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 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+。

证明从这里很容易证明，由正则表达式识别的每个实例都被语法识别，使用归纳法。

相关推荐