--/--/--

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
2012/10/16

コイン投げ問題3

問題

A氏とB氏が二人でコインを投げるゲームをします

コインを投げ続け、表表表裏が連続で出ればA氏の勝ち、
表裏裏裏が連続で出ればB氏の勝ちです

連続で出るまで投げ続けます
連続で出たらそこで試合終了です

さて、A氏の勝つ確率B氏の勝つ確率はそれぞれいくつでしょう?



前回同様、オートマトンを書いてみます

ここでオは表を、ウは裏を表しています
また状態AはA氏が勝利した状態
状態BはB氏が勝利した状態です

2012-10-16-2.jpeg


さてこいつをAが勝つパターン、
Bが勝つパターンに分けて、正規表現で表すとどうなるでしょうか

ここで僕が使ってる数式エディタは日本語が使えないので
表のことをO、裏のことをUと表すことにします

また、記号の右肩は繰り返し、
アスタリスク(*)は0回以上、
OプラスU(O+U)はOまたはUを意味します

これを踏まえて正規表現で表すと

Aが勝つパターン

となります。ここで、括弧の中は状態2を出発して状態2に戻るパターンを表現しています

ここで何通りもある正規表現のうち、同じ文字列を複数通りの解釈が出来るような正規表現を選ぶと
答えが変わってきます

たとえば一番最後がOであるような文字列を表現する正規表現は
ですが
と書いてもおっけーです(たぶん)

ところが最終的に受理する言語が同じでも意味は違います
後者の場合例えばOOOという言語は受理しますが

 と  を別物として受理します

1個めの正規表現ならとしてしか受理しないので重複がありません。

できるだけ{*}の内側に{*}が内容に注意して正規表現化したほうがいいと思います


さてさてAの勝ちパターンの確率を求めてみたいのですが、
随分と長くなってきたのでそれは次回にしておきましょう

コメント

非公開コメント

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。