语法生成的构造语言

Question

我们必须找到L(G)，其中文法G给出为-

S->AB|CD, A->aA|a ,B->bB|bC, C->cD|d, D->aD|AD

我试过这个问题，但它递归得非常深，我无法终止字符串。[我知道 A 将在 n 步后生成 a^n，但是 D、C、B 呢？]

到目前为止，我已经尝试过如下-

A->aA->aaA->....->a^(n-1)A (after n-1 steps)->a^n
B->bB->bbB->....->b^(m-1)B (after m-1 steps)->b^(m-1)bC->b^(m-1)bbC->...b^(m-1)b^(n-1)C->b^kC
C->cD->ccD->...->c^(p-1)D or c^(p-1)d[Thus we will consider as C->c^pD or C->c^pd]
D->aD->aaD->...->a^(q-1)D->a^(q-1)a^nD[Thus we will consider D->a^rD]

现在 B 依赖于 C，C 依赖于 D，而 D 依赖于自身（即 D 以 D->a^rD 的形式重复自身）

那么如何找到这种不终止的语言的语法呢？

Answer 1

D 不会产生一串终端，因此它是无用的，可以省略，包括所有具有 D 的规则。

简化语法为：

S->AB, A->aA|a ,B->bB|bC, C->d

语言将是：{a^m b^n d : m,n>=1}

语法生成的构造语言

Constructing Language generated by the grammar

grammar

automata

formal-languages