context-free-grammar - 以下上下文无关语法生成的语言和补语？

Question

G={ {S,A} , {a} , {S -> SAS | a , A -> aS | a} ,S}

在答案部分，它写道：

L(G) = {a, a3, a4, a6, a7} 和

L(G) 的补码写成： 。{a2, a5, a8, ...}

请帮助我了解上述语言及其补语是如何生成的？

我的尝试/分析：

上述文法的字符串至少应包含 3 个 a（否？），如：S-> SAS, 替换S --> a，A --> a在其中我们得到 , S --> aaa。但解决方案L(G)从a.

请帮助我理解这个概念，还是我解释错了。

另外，请解释是否有任何标准方法可以从任何语法中找出语言？我用谷歌搜索了很多，但找不到一般程序。提前致谢。PS-我正在为即将到来的竞争性考试做准备。

Answer 1

对于以下语法 G：

G = {{S, A}, {a}, {S -> SAS | a, A -> aS | a}, S}  

语言：

L(G) = {a, a3, a4, a6, a7}是不正确的。

字符串 a ⁵也是可能的。

a是可能的，因为有生产S --> a，

S- 产品是

S --> SAS 
S --> a    

和A- 产品是

A --> a
A --> aS 

L(G) 中的每个字符串都从 生成S。要将任何句子形式转换为句子，您必须应用A --> a或应用S --> a（奇数长度 1）。

从任何语法中找出语言的骗子方法是“按顺序生成树”。：

w要生成大于一个长度的字符串|w| > 1，您必须使用生产规则S --> SAS。

    T1:            T2:

     s             S
    /|\           /|\
   / | \         / | \  
  S  A  S       S  A  S 
  |  |  |      /  / \  \
  a  a  a     a  |   |  a
                 a   a 

⁴之后的下一个最小可能字符串仅是⁵：

    T3:  

     s             
    /|\           
   / | \         
  S  A   s       
 /  / \  |\
a  |   | a \
   a   a    a

所以⁵不能用L(G)' 的恭维语言。

编辑：

⁸的想法：

     T4:          

     s             
    /|\           
   / | \         
  S  A   S       
 /  / \   \
a  |   |   \
   a   a    T2  

来自 T2 的三个a+ 五个as = 八个as

语法语言：

L(G)= 是 { | 其中} ann != 2

补是唯一L(G)的{aa}！