- 締切済み
形式言語とオートマトン
文法G= ({S, A}, {a, b}, {S→aA, S→ab, A→ab},S) の全ての文形式は S, aA, ab, aabの4つみたいですが なぜS入るのにAは入らないのですか？
- qwsfgh
- お礼率30% (17/56)
- その他([技術者向] コンピューター)
- 回答数1
- ありがとう数1
- みんなの回答 （1）
- 専門家の回答
みんなの回答
- _kappe_
- ベストアンサー率68% (1522/2216)
開始記号がSの場合、AはS→aAのときにのみ出現してA単独で出現することがないからだと思います。
関連するQ&A
- 文脈自由文法をチョムスキー標準形に変換
大学の数学で分からない問題があります。 どなたか教えていただけないでしょうか？ １．次の規則を持つ文脈自由文法をチョムスキー標準形に変換せよ。 (1) G=({S,A},{ab},P,S) P={S→Ab,A→aAb,A→ab} (2) G=({S,A,B},{ab},P,S) P={S→aB,S→bA,A→a,A→aS,A→bAA,B→b,B→bS,B→aBB} (3) G=({S},{a,b},P,S) P={S→aS,S→aSbS,S→ε} ２．次の書き換え規則で定義される文法が生成する言語を示せ。 但し、「={S,A,B},Σ={0,1,2},開始記号はSとする。 (1) S→0AB,A→0AB|0B,B→1 (2) S→S0|AB,A→1A|1,B→2 (3) S→A,A→0A|0,B→B1|1 (4) S→AB.A→0A1|01,B→B2|2 問題は以上です。長くなってしまい申し訳ありません。 また、学校で何やっていたんだとお怒りの方もいらっしゃるかと思いますが、何卒よろしくお願いします。
- ベストアンサー
- 数学・算数
- ruby の nil エラー
rubyで１０Ｃ０～１０Ｃ１０までの値をすべて合計する 計算をさせようと思って作ったのですが。 定義はうまくできa(10,1)=10と計算できるのですが whileで合計させているところがうまくいきません。 関数的にはあっていると思うのですがnilエラーになってしまい ます。原因はなんなのでしょうか。。。 定義開始 ーーーーーーーーーーーーーーーーーーーーーー def a(g,h) puts a=1 b=1 while a<=g do b = b * a a = a + 1 end c=1 d=1 while c<=h do d = d * c c = c + 1 end e=1 f=1 while e<=g-h do f = f * e e = e + 1 end puts b / ( d * f ) end ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー 定義終了 aa=0 ab=0 while aa <= 10 ab=a(10,aa)+ab aa=aa+1 puts ab end これをすると ab=a(10,aa)+ab ここがNoMethodErrorと表示され 解がでません。 また、ab=a(10,aa)+ab これを ab=a(10,aa) こうすると 解がちゃんとでるのですが。 １ nil １０ nil ４５ nil ２１０ nil . . . となってしまいます。
- ベストアンサー
- Ruby
- 浜辺の歌の形式って・・・？？
浜辺の歌の形式って・・・？？ 浜辺の歌の形式は二部形式で合っていますでしょうか？ あと二部形式だったら AB（aa'ba') なのかAA'なのか・・・？ 教えて下さい！ お願いします。
- ベストアンサー
- 音楽
- 有限オートマトンの限界
文系の大学生ですが理系の学問も少しかじっていますが、全くわからないのです。 とくに教科書の有限オートマトンにかんするこの記述がよくわかりません 「有限状態機械で定義できる言語はかなり限定されている。 ab,aabb,aaabbb,・・・ のように文字aがn個続いた後、n個の文字bが現れるような文字列からなる 言語を定義することが出来ません」 え・・・なんでできないんですか・・・？そのあと文脈自由文法なら正規文法で書けなかったab,aabb,aaabbbのパターンの定義も書ける、と書いてあるのですが、それもよくわかりません。こんなオバカですけど、どうしても理解したいので、説明よろしくおねがいします！m(._.)mちなみにとても急いでいます！よろしくおねがいします！！
- ベストアンサー
- 科学
- 数Ｂベクトルの問題について
※ベクトル表記ができないので、ベクトルは隣に「→」を付けて表記します。 ＡＢ＝５、ＡＣ＝８、角ＢＡＣ＝60° である△ＡＢＣの三つの頂点から対辺へ下ろした三本の垂線の交点をＨとする。ＡＨ→＝aＡＢ→＋bＡＣ（a、bは実数）と表すと、ＢH→⊥ＡＣ→、ＣH→⊥ＡＢ→であるから、a、b間の二つの関係式…… と問題文は続きます。 ですが疑問はかなり初期段階のことなので、取り敢えずここまで書いて止めます。 解説は ＡH→＝aＡＢ→＋bＡＣ→ とすると ＢH→＝ＡH→－ＡＢ→ ＝（a－１）ＡＢ→＋bＡＣ→ という所から始まるのですが、この（a－１）になるというのが理解できません。 どなたか分かり易い解説お願いします。 なお補足させていただく場合がございます。
- ベストアンサー
- 数学・算数
- 二つのよく似たオートマトン
本に二つのよく似たオートマトン npda(=non-deterministic pushdown automaton)があります。 片方はΓ={0, 1}ですがもう片方はΓ={z, 1}です。 (1)npda for {a^n b^n: n>=0} ∪ {a} Q = {q0, q1, q2, q3} Σ = {a, b} Γ = {0, 1} ←大きな違い z = 0 F = {q3} q0: 'a's coming in ??? 自信なし q1: 'b's coming in ??? 自信なし …というか分かりません。 q2: 'b's going out ??? 自信なし q3: final state δ(q0, a, 0) = {(q1, 10), (q3, λ)} ←これは{a}の部分なので消せば(2)と同じになるはず δ(q0, λ, 0) = {(q3, λ)} δ(q1, a, 1) = {(q1, 11)} δ(q1, b, 1) = {(q2, λ)} δ(q2, b, 1) = {(q2, λ)} δ(q2, λ, 0) = {(q3, λ)} (2)npda for {a^n b^n: n>=0} Q = {q0, q1, q2} Σ = {a, b} Γ = {z, 1} ←大きな違い z = 無記入 F = {q2} q0: 'a's coming in q1: 'b's coming in q2: final state δ(q0, λ, z) = {(q2, z)} δ(q0, a, z) = {(q0, 1z)} δ(q0, a, 1) = {(q0, 11)} δ(q0, b, 1) = {(q1, λ)} δ(q1, b, 1) = {(q2, λ)} δ(q1, λ, z) = {(q1, z)} Γの"0"が"z"に入れ替わっただけかと思ったのですが ステート(=state, q0やらq1やら)の数も違いますし、入力の仕方も違います。 質問1. {a}の部分を除けば両者とも{a^n b^n: n>=0}になりますか? 質問2. もしそうであるならば、なぜΓを{0, 1}と{z, 1}などと変えているのですか? それはstatesの数に関係ありますか?
- ベストアンサー
- その他（プログラミング・開発）
- VBAでのデータ転記
データがsheet1に縦記述で書いてあります。 A01 A02 A03 . . B01 B02 B03 . . AA01 AA02 AA03 . . AB01 AB02 AB03 . . これをsheet2に以下のように並べ替えたいのです。 A01 A02 A03・・・ B01 B02 B03・・・ ・・・・・ AA01 AA02 AA03・・・ AB01 AB02 AB03・・・ Left関数で文字列の左1文字を前後のセルで比較して異なる場合、改行する方法を考えましたが、AA01 AA02・・・になると左から２番目の文字で判断しなければなりません。なにかいい方法はあるでしょうか？ ご指導宜しくお願いいたします。
- 締切済み
- オフィス系ソフト
- BASIC言語について。
数学のLET文は、なぜ、左辺と右辺は等しいという意味ではないのでしょうか？例えば、LET A ＝2なら、Aは2に等しいという意味だと思うのですが。長方形の面積は、LET S＝A*Bなら、面積Sは、A*Bに等しいという意味になると思うのですが。＝は、等しい以外に何か意味があるのでしょうか？教えていただけると幸いなのですが。
- ベストアンサー
- 数学・算数
- オートマトンと形式言語
オートマトンの問題で受理される語をどう答えていいかわかりません 状態変異図を見て判断するんですか？ 例えば下の有限オートマトンによって受理される言語L(M)を示せ という問題では答えはL(M)={ω∈{a}*|ωは3の倍数個のaからなる 語}になります。
- 締切済み
- 数学・算数
