语言和补语语言由以下Context语言生成？(Language and Complement language generated by the following Context free gram

语言和补语语言由以下Context语言生成？(Language and Complement language generated by the following Context free grammar?) G={ {S,A} , {a} , {S -> SAS | a , A -> aS | a} ,S}

在答案部分，其中写道：

L(G) = {a, a 3 , a 4 , a 6 , a 7 }和

L（G）的补充写为： {a 2 , a 5 , a 8 , ...} 。

请帮我理解上面的语言及其补充是如何产生的？

我的尝试/分析：

上述语法的字符串应至少为3个（不？）为： S-> SAS ，替换S --> a和A --> a得到它， S --> aaa 。 但解决方案L(G)以a开头。

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

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

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

In the answer section , its written:

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

Complement of L(G) is written as : {a2, a5, a8, ...}.

Please help me understand how is the above language and its complement generated?

My try/analysis:

String for the above grammar should be minimum of 3 a's (No?) as: S-> SAS , substitute S --> a and A --> a in it we get , S --> aaa. But the solution L(G) starts with a.

Please help me understand this concept or am I interpreting something wrong.

Also, PLEASE explain is there any standard approach to figure out the Language from any Grammar? I googled a lot but couldn't find a general procedure. Thanks in advance. PS-I'm preparing for a coming competitive exam.

最满意答案

对于以下语法G：

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

语言：

L(G) = {a, a ³ , a ⁴ , a ⁶ , a ⁷ } 不正确。

字符串a ⁵也是可能的。

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

S产品是

S --> SAS S --> a

A Productions是

A --> a A --> aS

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

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

生成比一个长度更大的字符串|w| > 1 |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)的恭维语言。

编辑：

^8的想法：

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

T2 = 8 a s三个a + 5个s

语法语言：

L(G) =是{ a ⁿ | 其中n != 2 }

L(G) 补充仅为{aa} ！

For following grammar G:

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

The language:

L(G) = {a, a³, a⁴, a⁶, a⁷} is not correct.

String a⁵ is also possible.

a is possible because there is a production S --> a,

S-productions are

S --> SAS S --> a

And A-productions are

A --> a A --> aS

Every string in L(G) generates from S. To convert any sentential form into sentence you have to apply either A --> a or S --> a that is (odd length 1).

The conman approach to figure out the Language from any Grammar is "Generate Tree in sequence". :

To generate strings w grater than one length |w| > 1, your have to use production rule S --> SAS.

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

Next smallest possible string after a⁴ is a⁵ only:

T3: s /|\ / | \ S A s / / \ |\ a | | a \ a a a

So a⁵ can't be in L(G)'s compliment language.

EDIT:

Idea for a⁸:

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

three a's + five as from T2 = eight as

Language of Grammar:

L(G) = is { aⁿ | where n != 2 }

Complement of L(G) is {aa} only!