人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

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

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

●質問者: gurugurucafe
●カテゴリ:学習・教育
✍キーワード:言語
○ 状態 :キャンセル
└ 回答数 : 1/1件

▽最新の回答へ

1 ● Sampo

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

1番の問題でしたら、

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

前者は

A -> 01

A -> 0A

A -> 0A1

後者は

B -> 0111

B -> B1

B -> 0B1

と表現できますね。

S -> A

S -> B

とすれば完成です。

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



●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ