- 締切済み
正規表現と状態遷移図
こんにちわ、お世話になっています。 それで正規表現を状態遷移図に直し方がうまくいかないのです。 たとえば(0+1)*のような正規表現があるとして状態遷移図は 状態数１つで初期状態と最終状態が同じになり1または0の値が入力？されると 矢印が自分自身に戻ってくるような感じでいいのでしょうか？（状態数２つ使うような気もするのですが＠＠；） 機械的にできるようなのですが参考書に書かれていないようなので＠＠； それともう１つ、1*(00)*の正規表現は初期状態と最終状態をq0とし２つの状態q1とq2からなる３つの状態数ので作ってみたのですがあっているでしょうか？図はのせられないので状態遷移表を書きます。 ちなみにDFAで状態数最小となるようにやってみました。 | 0 | 1 q0 | q1 | q0 q1 | q0 | q2 q2 | q2 | q2 ちなみにq0は0でq1、1でq0に遷移するという感じです。 みにくいかもしれませんがよろしくお願いします。
- ruruka777
- お礼率50% (7/14)
- 数学・算数
- 回答数2
- ありがとう数1
- みんなの回答 （2）
- 専門家の回答
関連するQ&A
- 正規表現とDFAについて
今回も正規表現のことについてなんですが＠＠； いきなりなのですが正規表現 １*((00)*+(11)*)と同じ言語を受理する 状態数最小の決定性有限オートマトンを構成せよという問題なのですが (1)まずこの正規表現が表しているのは初めに０個以上の１の列が続き その後に偶数個の0または1の列が続く、偶数個の0または1の列の後には 1もしくは0の列はこない。というような解釈でいいのでしょうか？ (2)問題の解き方なのですが自分としてはまず非決定性有限オートマトン(NFA) を作りそれを決定性有限オートマトンに変換して求めると思っているのですが あっているのでしょうか？ (3) (2)の解き方をするとまず状態遷移図を書きたいのですがなかなかうまくいきません。やはり慣れなどがあるのでしょうか？正規表現を見ただけですぐに状態遷移図が考えつかなく＠＠； それで自分なりにやってみたのですが状態遷移図は見にくいと思うので 状態遷移表みたいな感じで書きます。 初期状態はq0で最終状態はq3,q5にしています。 ※NFAからDFAに変換するための状態遷移表ではないです。 状態の集合 ｜ ０ ｜ １ ｜ ------------------------------------------------ q0 空集合 [q0,q1] q1 q2 q4 q2 q3 空集合 q3 q2 空集合 q4 空集合 q5 q5 空集合 q4 のような感じになったのですがなにか誤っているでしょうか？ なかなかイメージがつかめなくて； なんか表示がヘンになるかもです。 長文、駄文ですみませんがよろしくお願いします<(__)>
- ベストアンサー
- 数学・算数
- UML(状態遷移図の書き方)
現在、Webアプリを開発しています。 ある画面の状態遷移図を書こうとしているので質問です。 その画面には複数ボタンがあり、それらを押下するとサブ画面が開いたり、 ファイル出力されたり、その他の項目がDisabled/Enabledになったりします。 この画面の状態遷移図を書こうとした場合、何を状態として表現すればよいの でしょうか。この画面における状態って何？？？ 元の画面から以下の3つの状態に対して矢印を引っ張ればよいのでしょうか。 ・元の画面→サブ画面を開いた状態 ・元の画面→ファイル出力状態 ・元の画面→項目のDisabled/Enabled状態
- ベストアンサー
- その他（プログラミング・開発）
- チューリング機械の状態遷移図
h(x)=0(x=0のとき),定義されない(x>0のとき) のチューリング機械の状態遷移図を書け という問題なのですが、x>0のときというのが難しいです。 チューリング機械ではx≠0ということは指定できないですよね？ こういった場合はどのように書けばいいのでしょうか？ あと、「定義されない」ということなんですが最終的に空白なマスにとどまっていればいいのでしょうか？
- ベストアンサー
- 数学・算数
- 決定性有限オートマトンと正規表現
現在オートマトンの勉強をしていますが，どうしても分からない問題がありました． 決定性有限オートマトンについて，初期状態，受理状態共に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* となりました． ご教授よろしくお願いします．
- 締切済み
- 科学
- 正規表現であるStringの集合を定義する
次の特徴を持つStringの集合を定義する正規表現Ｑはどのように表せばいいでしょうか？ １．0と1のみを使うString ２．「接頭辞」の0の数が1の数より２つ多くない ３．「接頭辞」の1の数が0の数より２つ多くない 接頭辞とはあるStringの先頭から始まる全てのsubstringのことです。例として123456789の接頭辞は"", 1, 12, 123, 1234, 12345, ..., 123456789となります。 この正規表現Ｑによって定義されるStringの集合の例として "", 10, 01, 0101, 1010, ... 正規表現Ｑで定義できない集合の例は 0011, 1100, 1110100, 10101100, ... 0011には接頭辞00が存在し、これは0の数が1の数より２つ多いので（0の数は２で1の数は０）正規表現Ｑでは定義できません。 これは不可能でしょうか？不可能の場合文脈自由文法で定義は可能でしょうか？
- ベストアンサー
- その他([技術者向] コンピューター)
- スレッドの状態遷移について。。。
Javaの本を買って読んでいます。 その中の「スレッド」のカテゴリーの「状態遷移」のところの「synchronized」の部分に、こう書かれています。 -------------------------- ・・・・・・ なお、sleepメソッドでスリープ状態（実行不可能状態）になったスレッドはロックを保持したまま開放しません。 そのため、ロックを取得できないで待たされるスレッドも実行不可能状態へ移行させられます。 -------------------------- これは、Synchronized指定されたメソッド（同期メソッド）の部分で出てきた文章でして、 私は、こう解釈しました。 → 例えば、同じオブジェクトの参照を引数とするスレッドが３つあり、その中の１つが『実行中』状態にある（仮に t１ とする）として（つまり残り２つ（ t２ t３ ）は『実行可能状態（プール）』にある。）、 実行中の t１ がsleep()メソッドで『実行不可能状態』になった場合、 『実行可能状態』にあった、t２ t３ も『実行不可能状態』へ移行する事になる。 間違っていますか？ もし、この解釈が正しければ、こうなりますよね？ t１・・・・・・・『実行中』 → 『実行不可能状態』 t２ t３・・・『実行可能状態』 → 『実行不可能状態』 ところが、状態遷移の５つの状態の図を見ると、 『実行可能状態』 から 『実行不可能状態』 へは、矢印→が書かれておりません。（逆向きの矢印がありますが。） どういう意味でしょうか。 java初心者ですが、 解りやすく教えて頂けると助かります。 宜しくお願い致します。
- ベストアンサー
- Java
- 正規表現について
お世話になります。 ●●● ●●● という文字列かどうか判断する正規表現を作成したいです。 条件としては、 ・「文字１ （←全角スペース）文字２」という感じで、文字１と文字２に全角スペースが挟まれている感じで、文字列の先頭にも末尾にも空白文字は入ってはいけない（真ん中に１つのみ） ・文字１と文字２には、数字・空白以外の文字が入る（主に感じ・ひらがな・カタカナが入る）（文字数は一文字以上） といったところです。 自分で作成した正規表現は、 $pattern = '/^([\d\S])+ ([\d\S])+$/'; if( !preg_match($pattern,$chkStr) ) print "マッチしていない"; } なんですが、どうもマッチしてほしい文字にマッチしていないようなのです。 お手数ですがご教授ください。
- ベストアンサー
- PHP
- 正規表現が組み立てれません・・・
URLのRewriteをしようと思うのですが、いまいち正規表現がわかりません。 調べながら作っているのですが、前方一致の否定のところでつまずきました。 条件は以下の通りです。 ○ 拡張子は.htmlもしくはaspxのみ ○ 前方にsub/ではないこと 条件は少なく割りと簡単に作れると思っていたのですが・・・ 私が作ったのはこんな感じです。 (?!(sub\/))(.*)(\.html|\.aspx|/$) しかし、これだと sub/aaa/bbb.html でチェックしたところ ub/aaa/bbb.html としてヒットしてしまいます。 最終的な目的は aaa/bbb.html はヒットする sub/bbb.html は先頭がsub/から始まってるのでヒットさせない と言った感じにしたいです。 前方一致の否定とは一体どのようにするのでしょうか *** 環境 *** Windows Server R2 2008 IIS 7.5 Rewrite Module サーバーの設定ですが正規表現はプログラミングで使う機会が多いのでこちらの方のカテゴリーにさせて頂きます。
- ベストアンサー
- その他（プログラミング・開発）
- オートマトンNFAからDFAへの変換
NFA(non-deterministic automaton)について質問させてください。 NFAからDFAへ変換するプログラムを作っています。 NFAの文法(状態数、アルファベット数、状態遷移表、終了状態）を別のデータファイルに入力し、それをプログラム中に読み込んで、NFAを登録したいと考えています。 しかし、状態遷移表だけがどのように取り込んでいいのか分からず途方に暮れています。 どうか教えていただけないでしょうか？ よろしく御願いいたします。 ファイルの中身（状態遷移表）としては、このような感じを考えています。 例えば、状態が３つ(q0, q1, q2)、３つのアルファベット(a,b,c)とε 0,1,2 E E E E 1 E E E E 2 1 q1から文字aのときにq0,q1,q2にそれぞれいくという意味。Eは何もなしという意味です。
- ベストアンサー
- C・C++・C#
お礼
よく考えてみると又違っているみたいですね＠＠； 前回同じ質問をさせてもらった時は状態数３つでできるようなことを言われて いたと思われますが３つでできるのでしょうか？ なんか４つになってしまったのですが。。。。。
補足
返信遅くなりました、回答ありがとうございます！ それで指摘があった所を直してみたのですがこのような感じで いいのでしょうか？ 1*(00)*の状態遷移表 qoは初期状態 q0とq2は最終状態 | 0 | 1 q0 | q1| q0 q1 | q2| q1 q2 | q1| q1 のような感じでいいのでしょうか？