文脈自由言語Ｌから文脈自由文法Ｇを求める方法を教えてください

文脈自由文法とプッシュダウンオートマトンを相互に変換するアルゴリズムというのなら存在しますが、お示しの課題のように自然言語的に表現された文法を機械的にCFGに変換するのは無理です。人間がプログラミングしなくてはいけません。

1番の問題でしたら、

• i>j-1なる0_i1_jを作る非終端記号
• i<j-1なる0_i0_jを作る非終端記号

をそれぞれ作ることを考えましょう。

前者は

A -> 01

A -> 0A

A -> 0A1

後者は

B -> 0111

B -> B1

B -> 0B1

と表現できますね。

S -> A

S -> B

とすれば完成です。

http://q.hatena.ne.jp/answer