- ベストアンサー
正規表現を入力するとオートマトンを出力するプログラム
大学の授業の課題で正規表現を入力するとオートマトンを出力するプログラムを書け、またはどのようなプログラムを作れば良いか説明せよ。という問題がでて困っています。 担当者の先生に質問したところ、参考書におおまかなプログラムの流れが載っていると言っていました。 その後、図書館などに行って調べたのですがオートマトンの定義や正規表現とはどういうものという感じのことしか書いてない本が多く、どのようなプログラムを作ればよいか全然わかりません。 やはり和書にはそのような本はないのでしょうか？ アドバイスやおすすめの本があったらおねがいします。
- gosutero
- お礼率77% (138/177)
- その他（プログラミング・開発）
- 回答数1
- ありがとう数1
- みんなの回答 （1）
- 専門家の回答
質問者が選んだベストアンサー
ありますよ。 セジウィックの本にもあるし…。(§20「パターン照合」のところ。) http://www.amazon.co.jp/exec/obidos/ASIN/4764902222/ (C言語版もあり) あと、これはお勧めしたくないのですが、 『定本Cプログラマのためのアルゴリズムとデータ構造』 http://www.amazon.co.jp/exec/obidos/ASIN/4797304952/ にもあります。 なぜお勧めしたくないかというと、いい本過ぎて、サンプルまで載っていて、 勉強にならないのではないかと思うからです。 その点を除けば、めちゃくちゃいい本で、 買って絶対損はしません。
関連するQ&A
- 決定性有限オートマトンと正規表現
現在オートマトンの勉強をしていますが，どうしても分からない問題がありました． 決定性有限オートマトンについて，初期状態，受理状態共にp，入力信号を0,1とする． 状態遷移表が以下の時，受理する言語を表す正規表現を求めよ． 0 1 p | p r q | p r r | q r 答え (0*11*0(11*0)*0)*0* という問題なのですが，状態消去法で自分でやってみても全然この答えになりません． ちなみに自分の解答は (0*1(1+01)*00)*0* となりました． ご教授よろしくお願いします．
- 締切済み
- 科学
- 3のべき乗の2進数表現全体は正規表現で書ける?
オートマトン理論の本の練習問題を解いていて以下のような疑問に行き当たりました。 アルファベット{0, 1}上の語を2進数とみなすとき、 2のべき数については 2のべき乗の2進数表現の全体 -> 10* 4のべき乗の2進数表現の全体 -> 1(00)* 8のべき乗の2進数表現の全体 -> 1(000)* ... というように正規表現で書くことができますが、「xのべき乗」のxが2のべき数以外のときにこのように正規表現で表せる場合は存在するのでしょうか? とりあえずx=3や5で小さい方から20個程べき数を列挙し、それらを受理する有限オートマトンを作ろうとしたのですが、私の能力では出来ませんでした。そこで不可能であることを証明することに方針を変えたのですが、そちらもまだ出来ないでおります。 どなたかこの問題を御教示いただけないでしょうか。 どうぞよろしくお願いいたします。
- ベストアンサー
- 数学・算数
- 正規表現とオートマトンについての問題です。
正規表現とオートマトンについての問題です。 下記の決定性有限オートマトンMが受理する言語L（M)を正規表現で表したい。以下のカタカナ に入る記述を穴埋めしなさい。 状態iから状態ｊに、kより大きな数字の状態を通らないで遷移させる入力文字列の集合をkRij と表すと、一般的に、 kRij = k-1Rik(k-1Rkk)*k-1Rkj∪k-1Rijと表される。 そこで、L(M)とは、初期状態1から受理状態3へ3より大きな数字の状態を通らないで遷移させる 入力文字列の集合のことであるから、 L(M) = ア = 2R13(2R33)*2R33∪2R13 ・・・・・(1) と書ける。(1)式は2R13でくくると、 L(M) = 2R13((2R33)*イ∪ウ) ・・・・・(1') となるが、一般に文字列集合をAとするとき、 A* = エ∪A1∪A2∪A3∪ ・・・ と定義され、 A*A = (オ∪A1∪A2∪A3∪ ・・・ )A = A1∪A2∪A3∪A4∪ ・・・ となり、 従って、A*A∪{ε} = A*A ∪ A0 = A* ・・・・・(2) である。よって(1')式は、 L(M) = 2R13(2R33)* ・・・・・(1'') と簡単化される。(1'')式の、まず2R13を求める。 2R13 = カ(1R22)*キ∪1R13 ここで、ク = 0R11(0R11)*0R12∪0R12 = {ε}{ε}*{1}∪ケ = コ 1R22 = 0R21サ0R12∪0R22 = シ{ε}*{1}∪{ε,1} = {ε,1} 1R23 = 0R21(0R11)*0R13∪0R23 = φ{ε}*ス∪{0} = {0} 1R13 = 0R11(0R11)*0R13∪セ = {ε}ソ{0}∪タ = チ 故に 2R13 = ツ{ε,1}*{0}∪テ ここで、{ε,1}* = トだから 2R13 = {1}ナ{0}∪{0} = ({1}ニ∪{ε}){0} ・・・・・(3) 次に2R33については 2R33 = ヌ(1R22)*1R23∪1R33 ここで、 ネ = 0R31ノ0R12∪0R32 = φ{ε}*{1}∪φ = ハ 1R33 = 0R31(0R11)*0R13∪0R33 = φ{ε}*{0}∪{ε,ヒ} = {ε,フ} 故に 2R33 = φ{ε,1}*{0}∪{ε,0}=ヘ 従って(1'')式は、(3)(4)式から L(M) = ({1}ホ∪{ε}){0}{ε,0}* 上式()内は(2)式と同様の理由からマであり、{ε,0}* = ミであるから L(M) = ム{0}メ これを正規表現すれば L(M) = モ0ヤ となる。 -----答え----- ア=3R13 イ=? ウ=? エ=A^0 オ=A^0 カ=1R12 キ=1R23 ク=1R12 ケ={1} コ={1} サ=(0R11)* シ=φ ス={0} セ=0R13 ソ={ε}* タ={0} チ={0} ツ={1} テ={0} ト=? ナ=? ニ=? ヌ=1R32 ネ=1R32 ノ=(0R11)* ハ=φ ヒ=0 フ=0 エ=?ホ=?マ=?ミ=?ム=?メ=?モ=?ヤ=? 途中までは解けたんですが?の箇所がわかりません・・・ よろしくお願いします。
- ベストアンサー
- 情報工学
- このオートマトンの問題
∑={0,1}上の言語L1,L2について L1：0を含まないか、0を3の倍数個だけ含む全ての文字列からなる集合 L2：1を含まないか、1を偶数個だけ含む全ての文字列からなる集合 （a）L2を長さ9以内の正規表現で表わし、その長さも書け。 (b)L1∩L2を受理する決定性有限オートマトンの状態遷移図を示せ。 正規表現は拡張BNFで定義されています (a)は(0+(1+0*)1)*と書けそうかなと思います（間違いかもしれません）が、長さはいくつになるのでしょうか？ (b)はどのようになるのでしょうか？あるいはどのように考えればよいのでしょうか？ 分かる方みえましたら教えて下さい。
- 締切済み
- その他([技術者向] コンピューター)
- Javaプログラム内の正規表現
スパイダーツールという技術(？)をつかって、 (あらかじめプログラミング言語で、使用者の必要な情報のみを検索し、出力してくれるというもの。言語はJavaでできています。) ヤフーファイナンスの値上がり/値下がり率ランキングを自分仕様にして利用しようと考えています。 その場合、Javaプログラム内に正規表現で書かれている部分があって、そこも書き換えが必要のようなんです。 しかし正規表現となると、不得意なJavaよりももっと理解不能！ …そこで質問です。 日本語→英文 英文→日本語 と直せる翻訳サイトのように、正規表現も翻訳できるサイトありませんか！？ もしくは正規表現について、分かりやすいサイトをご存知の方はご一報をどうぞ宜しくお願い致します。
- ベストアンサー
- Java
- 正規表現
すいません。もう一度質問します。 Ｃ言語で「正規表現」プログラムしたいです。 「[0-9]」や「[a-z]」の検知をどのようにプログラムしたらいいかアドバイスください。 問題は『「.」は任意の文字一文字が存在することを示し、「*」はその前の文字の任意の繰り返し（1回もあり）「[文字-文字]」はその中のいずれかの文字の存在を示す。 これらを用いて「b.c」（argvを用いてキーボード入力）ならb1c、bsc、bah等を、「6*」なら6、66、6666等の存在する行（ファイルをよみこんで）を出力するプログラムをＣで書け。』ということです。 なかなか分かりません。 むずかしいです。
- ベストアンサー
- C・C++・C#
- 正規表現のエラーを区別したい
Delphi XE5を使って正規表現のプログラムを作りました。 ... try result_txt := TRegEx.Replace(target, pattern, replace, []); AddButton.Enabled := True; except ShowMessage('正規表現にエラーがあります'); end; ... というようなプログラムですけど、この正規表現のエラーをもう少し詳しく表示できないでしょうか？ （正規表現のエラーコードはいくつかに分かれていないでしょうか？） 正規表現のテストプログラム部分で、target、pattern、replaceともユーザーが入力するようになっています。
- ベストアンサー
- その他（プログラミング・開発）
- Unixについて
大学のレポートで理解不能で困っています（＞０＜） 「Unixにはlexという字句解析用のプログラムがある。lexは正規表現を入力して与えると正規表現の照合を行うオートマトンを作ってそれをシュミレーションするｃのプログラムを出力する。正規表現に合致する文字列が現れたときに実行すべき動作をｃプログラムの形で与えることもできる。lexの仕様を調べてその実現方法を検討しなさい。」よろしくお願いします
- 締切済み
- その他（プログラミング・開発）
- 正規表現でのマッチング
連想配列%hushがあります。 %hushの中のキーが「a何とか」、つまり a0、a1、a2、a3、・・・ の値だけを、配列@arrayに格納します。 つまり $array[0]=$hush{'a0'} $array[1]=$hush{'a1'} $array[2]=$hush{'a2'} $array[3]=$hush{'a3'} ・・・ といった感じにしたいのですが、 「a何とか」は正規表現を用いて a.* と表現できます。 ってここまでは手元の本で分かったのですが、マッチングのif文をどう書けばいいんだよ！ if($key==a.*) と書いてもうまくマッチしてくれないんで、a.*を""で括ってみたり()で括ってみたりするものの相手にされず・・・ 手元の本は「こういう場合正規表現ではこう書けば良くて、これをマッチングさせれば良い」みたいなことを書いていますが、マッチングのさせ方は書いていません。 プログラムの文法書を読むと、条件分岐の仕方は書いていますが、==演算子の右側が正規表現だった場合の使い方は書いていません。 あるいは、正規表現の場合のマッチングはif文などを用いないのでしょうか？ だったら正規表現の本にマッチングの文法を書いていますよね！？ なんだかんだでマッチングがうまくいかないのです。 この場合、どう記述すればいいのでしょうか？ お手数をお掛けします。
- ベストアンサー
- その他([技術者向] コンピューター)
お礼
liarさん回答ありがとうございます。 オートマトンや正規表現などで探していました。 早速買ってきました。 サンプルと同じものを作らないようにしたいと思います。