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、aaaaIIIIIIE などのように数えます。その状態に達したときはいつでも、カウントを続けるか終了するかを常に決定します。

数え続けるときは、"a" を I 倍し、同時に "I" を (I+2) 回する必要があります。ただし、「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