言葉を紡げ! | spin on the RITZ

言葉を紡げ!


【問題】

言語Lを生成する文法を構成しなさい。



とりあえず、aをフィボナッチ数個だけ並べりゃ良いわけです。

大学からのバスが来るまでに解けるだろうとたかをくくっていたんですが、どうも上手くいかない。



しょうがないので、答えを見ることに。


【解答】

生成規則Pは下記の様になる




これ、フツーに思いつかないだろ・・・・・・・・・・・・

俺が馬鹿なのかッ!だからなのかッッ!!!



適当にシミュレーションしてみます(バーの代わりにダッシュをつけます)


S

↓(S→A'B')

A'B'

↓(A'→A'C)

A'CB'

↓(A'→a)

aCB'

↓(CB'→BB')

aBB'

↓(aB→aa)

aaB'

↓(aB'→aa)

aaa


一応、出来てる、みたい、だな。。



テスト不安になってきたぞww


線形拘束オートマトンの説明があんまりなかったので、自分で調べねば