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


例えば
http://www.cs.shinshu-u.ac.jp/~yamamoto/Lecture/automaton/doc/enshu9.pdf
のような問題の解法です

回答の条件
  • URL必須
  • 1人2回まで
  • 登録:2006/07/24 21:24:54
  • 終了:2006/07/26 14:45:34

回答(1件)

id:Sampo No.1

Sampo回答回数556ベストアンサー獲得回数1042006/07/25 11:12:44

ポイント10pt

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

1番の問題でしたら、

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

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

前者は

A -> 01

A -> 0A

A -> 0A1

後者は

B -> 0111

B -> B1

B -> 0B1

と表現できますね。

S -> A

S -> B

とすれば完成です。

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

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません