theory - 特定语言的上下文相关语法

Question

嘿，我已经被这个问题困扰了几天，甚至在我的教科书中查看示例问题以及示例解决方案，我无法弄清楚如何使这个语法起作用。

给出该语言 L 的语法：

L = { a^n^2 : n ≥ 0 }

我知道这可能是一个模糊的问题，但我真的可以使用一些帮助来解决这个问题。

提前致谢！

Answer 1

我的回答可能来晚了。我希望它对您（或其他读者）有用。

S -> a
S -> aIIIE

Finish counting:

aII -> aaFI
aFII -> aaFI
aFIE -> aa


Going on counting:

Produce "a"s and "J"s
aII -> aCaLPI
PII -> aLPI
PIE -> aRRRE

Move ALL "a"s to the left:
La -> aL
LR -> RR
Ca -> aC

Convert "R"s to "I"s:
CR -> IC
CE -> E

州名：

S : Start
E : "End"
I : "1" 
F : "Finish"
P : "Produce"
L : "Left"
R : "Right"
C : "Convert"

解释：

让我也勾勒一下解决方案的想法。平方数总是奇数序列的总和。例如 2^2=1+3=4、3^2=1+3+5=9 等等。

数学上：“在 1 和 n 之间对 k 的 2*k-1 求和”= n^2

你实际上需要做的只是数奇数。这说起来容易做起来难。

我的语法是这样的：

在左侧，您有先前的结果。下一个奇数由同一个非终端的奇数表示（在我的例子中是“I”）。所以我算作 aIIIE、aaaaIIIIE 等等。每当您达到该状态时，您总是决定是继续计数还是完成计数。

当您继续计数时，您需要产生 I 次“a”，同时再次产生 (I+2) 次“I”。然而，“I”和“a”将按照它们的顺序混合。因此，您必须引入一些将所有“a”向左移动（以及所有“I”向右移动）的机制。此外，您必须始终限制产生单词的自由，以使您的“当前路径”无论如何都不能离开。否则，您的生产可能会陷入僵局。（“F”、“P”、“L”、“R”、“C”、“E”为此服务。）

我想用 n=2 和 n=3 来演示它。这应该足够了。

"*->" : "产生"

n=2：

aIIIE
(aII)IE *-> (aaFI)IE
a(aFII)E *-> a(aaFI)E
aa(aFIE) *-> aa(aa)
aaaa

n=3：

aIIIE
(aII)IE *-> (aCaLPI)IE
aCaL(PII)E *-> aCaL(aLPI)E
aCaLaL(PIE) *-> aCaLaL(aRRRE)
a(Ca)LaLaRRRE *-> aaCLaLaRRRE
aaCLa(La)RRRE *-> aaCLa(aL)RRRE 
aaCLaa(LR)RRE *-> aaCLaa(RR)RRE
aaC(La)aRRRRE *-> aaC(aL)aRRRRE
aaCa(La)RRRRE *-> aaCa(aL)RRRRE
aa(Ca)aLRRRRE *-> aa(aC)aLRRRRE
aaa(Ca)LRRRRE *-> aaa(aC)LRRRRE
aaaaC(LR)RRRE *-> aaaaC(RR)RRRE
aaaa(CR)RRRRE *-> aaaa(IC)RRRRE
aaaaI(CR)RRRE *-> aaaaI(IC)RRRE
aaaaII(CR)RRE *-> aaaaII(IC)RRE
aaaaIII(CR)RE *-> aaaaIII(IC)RE
aaaaIIII(CR)E *-> aaaaIIII(IC)E
aaaaIIIII(CE) *-> aaaaIIIII(E)
aaaaIIIIIE