• ベストアンサー

有限オートマトンの限界

文系の大学生ですが理系の学問も少しかじっていますが、全くわからないのです。 とくに教科書の有限オートマトンにかんするこの記述がよくわかりません 「有限状態機械で定義できる言語はかなり限定されている。 　　ab,aabb,aaabbb,・・・　 　のように文字aがn個続いた後、n個の文字bが現れるような文字列からなる 　言語を定義することが出来ません」 え・・・なんでできないんですか・・・？そのあと文脈自由文法なら正規文法で書けなかったab,aabb,aaabbbのパターンの定義も書ける、と書いてあるのですが、それもよくわかりません。こんなオバカですけど、どうしても理解したいので、説明よろしくおねがいします！m(._.)mちなみにとても急いでいます！よろしくおねがいします！！

  • 科学
  • 回答数2
  • ありがとう数3

質問者が選んだベストアンサー

  • ベストアンサー
回答No.2

何個あるかわからないaの個数を記憶するメカニズムが必要だからです。

miso-miso
質問者

お礼

なるほどー！わかりました、ありがとうございました！

その他の回答 (1)

  • masa0720
  • ベストアンサー率26% (18/68)
回答No.1

今学校でオートマトンを習っている理系の学生ですが、これはaが出ないとbが出られないわけです。つまりaが無限だったらいつまで経ってもbが出られないので、限定されてくるのだったと思います。 間違っていたらごめんなさい。

miso-miso
質問者

補足

早速のご回答ありがとうございました！ しかし、せっかく説明していただいたのに、それでも解らないんです・・・ なぜaが出ないとbが出られないのでしょうか。 そこがよく解らなかったです。 ぜひ教えてください！

  1. カテゴリ
  2. 学問・教育
  3. 自然科学
  4. 科学

関連するQ&A

  • オートマトンが分かりません！！

    現在情報関係の大学に通っていて、もうすぐ『オートマトンと言語理論 』という科目のテストがあります。教科書は森北出版で著者が富田悦次・横森　貴の『オートマトン・言語理論』を使っています。テスト範囲が有限オートマトンと正則表現／言語と形式文法のところなんですが正直まったく内容が理解できないです。そこの範囲を例題などを中心に初心者でも分かりやすく書いてあるオススメの参考書を知っていたら教えてください！

  • このオートマトンの問題

    ∑={0,1}上の言語L1,L2について L1：0を含まないか、0を3の倍数個だけ含む全ての文字列からなる集合 L2：1を含まないか、1を偶数個だけ含む全ての文字列からなる集合 （a）L2を長さ9以内の正規表現で表わし、その長さも書け。 (b)L1∩L2を受理する決定性有限オートマトンの状態遷移図を示せ。 正規表現は拡張BNFで定義されています (a)は(0+(1+0*)1)*と書けそうかなと思います（間違いかもしれません）が、長さはいくつになるのでしょうか？ (b)はどのようになるのでしょうか？あるいはどのように考えればよいのでしょうか？ 分かる方みえましたら教えて下さい。

  • ある言語クラス判定問題(正規言語?文脈自由言語?)

    形式言語に関する以下の問題に悩んでおります。 問題: Lを正規言語とするとき、以下の言語L1, L2はそれぞれ(1)-(5)のどれに該当するか? L1={xy | xとyは共にLの元で、長さが同じ(|x|=|y|, x in L, y in L)} L2={xy | xとyは共にLの元で、xの長さはyの長さの2倍(|x|=2|y|, x in L, y in L)} (1)正規言語である (2)正規言語ではないが、文脈自由言語である (3)文脈自由言語ではないが、文脈依存言語である (4)文脈依存言語ではないが、帰納的可算言語である (5)帰納的可算言語ではない 直観的には(有限オートマトンは数を数えられないので)L1もL2も正規言語ではないと思うのですが、私の力では証明することが出来ないでおります。 ヒントや部分的回答(e.g. ひとまず(1)ではない。理由はかくかくしかじか)でもありがたいですので、どうぞよろしくお願いいたします。

  • 計算理論についての質問

    計算理論についての質問です。 文脈自由文法gがεを受理するかどうかを判定するアルゴリズムが必ず存在するか、しないかを証明するという課題が出たのですが、 「アルゴリズムが存在する」ということはどうやったら証明できるのでしょうか？ 今、手元にはホップクロフトの「オートマトン言語理論計算論」があるのですが、「アルゴリズムが存在するかどうか」を証明するような問題が見つかりません。 学校でもこのような問題の例題はやっていないので、どなたか教えてください。 よろしくお願いしますm(__)m

  • 「論理的思考」は、数学など理数系の学問によって養わ

    「論理的思考」は、数学など理数系の学問によって養われるものだと言われますが、文系の法律学や経済学の中で使われる論理的思考も、理数系の考え方がベースになっているのですか？それとも、理系で数字を使って行う論理的思考と文系で言語を駆使して行う論理的思考はそもそもモノが違うのでしょうか？

  • 有限オートマトン

    有限オートマトンという言葉すら聞いたことがないのにいきなり宿題を出されました。調べてもわからないので助けてください。 解答そのものは自分で考えるので、初心者にわかりやすいヒントをいただけないでしょうか？ １．２つの2進数の加算を行う有限オートマトンを示しなさい。 ２．任意の桁の乗算は有限オートマトンによって実現不可能なことを説明しなさい

  • 正規表現とオートマトンについての問題です。

    正規表現とオートマトンについての問題です。 下記の決定性有限オートマトン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 エ=?ホ=?マ=?ミ=?ム=?メ=?モ=?ヤ=? 途中までは解けたんですが?の箇所がわかりません・・・ よろしくお願いします。

  • 有限オートマトン

    有限オートマトンの問題で， 「任意の有限オートマトンAとBについて， T(A)＝T(B)が成立するかどうかを判定できるか． ただしT(A)，T(B)とは有限オートマトンA，Bが それぞれ認識する言語のことである．」 というのがあるのですが，まったく方針がたたなくて 困っています．どなたかよろしくお願いします．

  • 有限オートマトンの読み方

    有限オートマトンの読み方がいまいち理解できません。 平成15年 秋期 基本情報技術者 午前　問10　 http://情報処理試験.jp/FE15b-am/t10.html 解説を見ても理解できません。 http://情報処理試験.jp/FE15b-am/t10a.gif おしえてください。

  • どの学部に行けばパラドックスについて深く学べるのか？

    『パラドックス』という理論(?)に凄く興味を持っていて、もっと深く勉強したいな～と思っています。 大学は自分の学問へ取り組む姿勢がメインなので、勉強しようと思えばどこの学部でも独学でやれるとは思っていますが 出来ることなら専門的な講義を受けたり、大学院などでの研究をしたいとも思っています。 パラドックスがどの学問に定義されているのかがよくわからないので、どなたかご存知の方いらっしゃらないでしょうか？ それとも、パラドックスというのはありとあらゆる学問で研究できるものなのでしょうか？ 誕生日のパラドックスやシュレディンガーの猫あたりは理系な感じがするのですが、嘘つきパラドックスなんかは文系っぽい感じがします。 どうぞよろしくお願いしますm(_ _)m

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する