計算論についての質問:抽象的な問題について
- 計算論の問題なのですが抽象的?なので良く分かりません(>_<) regular grammars: G1, G2 1.L(G1)⊆L(G2)を判断するalgorithmは? 2.L(G1)=L(G2)を判断するalgorithmは? 3.DFA: A1, A2 L(A)=L(A1)∩L(A2)となるDFAAを作れ。 という問題なのですが… 自分で分かったのは、 regular grammars: G1, G2 L(G)=∅を判断するalgorithm等です。 今までに習ったことは、REG、CF、オートマトン等です。 考え方が全く分からないのでどなたかお願いしますm(__)m
- 計算論に関する抽象的な問題について質問があります。具体的には、以下の問題についてのアルゴリズムを教えていただけると助かります。1. G1とG2という2つの正規文法があり、L(G1)⊆L(G2)を判断するアルゴリズムは何ですか?2. G1とG2が与えられたとき、L(G1)=L(G2)を判断するアルゴリズムは何ですか?また、3つ目の問題として、A1とA2という2つのDFAが与えられた場合、L(A)=L(A1)∩L(A2)となるDFA Aを作成する方法について教えてください。自分でREG、CF、オートマトンに関する考え方を使っても答えにたどり着けませんでしたので、どなたかお力添えいただけると幸いです。よろしくお願いします。
- 計算論における抽象的な問題についての質問です。具体的には、正規文法とDFAに関する問題についてのアルゴリズムや作成方法について教えてください。1つ目の問題では、与えられた正規文法G1とG2に対して、L(G1)⊆L(G2)を判断するアルゴリズムについて教えてください。2つ目の問題では、G1とG2が与えられた場合に、L(G1)=L(G2)を判断するアルゴリズムについて教えてください。そして、3つ目の問題では、2つのDFA A1とA2が与えられたときに、L(A)=L(A1)∩L(A2)となるDFA Aを作成する方法について教えてください。これまでREG、CF、オートマトンに関する考え方を学んできましたが、どうしても答えにたどり着けませんでした。お力添えいただけると助かります。
- ベストアンサー
計算論についての質問です。
計算論の問題なのですが抽象的?なので良く分かりません(>_<) regular grammars: G1, G2 1.L(G1)⊆L(G2)を判断するalgorithmは? 2.L(G1)=L(G2)を判断するalgorithmは? 3.DFA: A1, A2 L(A)=L(A1)∩L(A2)となるDFAAを作れ。 という問題なのですが… 自分で分かったのは、 regular grammars: G1, G2 L(G)=∅を判断するalgorithm等です。 今までに習ったことは、REG、CF、オートマトン等です。 考え方が全く分からないのでどなたかお願いしますm(__)m
- apple_cube
- お礼率47% (127/268)
- 数学・算数
- 回答数1
- ありがとう数0
- みんなの回答 (1)
- 専門家の回答
質問者が選んだベストアンサー
以下、A^c は A の補集合の意。 >1.L(G1)⊆L(G2)を判断するalgorithmは? L(G1)⊆L(G2) ⇔ L(G1)∩(L(G2))^c = (空集合). >2.L(G1)=L(G2)を判断するalgorithmは? L(G1)=L(G2) ⇔ (L(G1)∩(L(G2))^c) ∪ ((L(G1))^c ∩ L(G2)) = (空集合). >3.DFA: A1, A2 >L(A)=L(A1)∩L(A2)となるDFAAを作れ。 ホップクロフト「オートマトン言語理論 計算論I」の定理3.3を 見てください。この本をお持ちでしたよね。
関連するQ&A
- 計算理論についての質問
計算理論についての質問です。 文脈自由文法gがεを受理するかどうかを判定するアルゴリズムが必ず存在するか、しないかを証明するという課題が出たのですが、 「アルゴリズムが存在する」ということはどうやったら証明できるのでしょうか? 今、手元にはホップクロフトの「オートマトン言語理論計算論」があるのですが、「アルゴリズムが存在するかどうか」を証明するような問題が見つかりません。 学校でもこのような問題の例題はやっていないので、どなたか教えてください。 よろしくお願いしますm(__)m
- ベストアンサー
- 数学・算数
- オートマトンと形式言語
オートマトンの問題で受理される語をどう答えていいかわかりません 状態変異図を見て判断するんですか? 例えば下の有限オートマトンによって受理される言語L(M)を示せ という問題では答えはL(M)={ω∈{a}*|ωは3の倍数個のaからなる 語}になります。
- 締切済み
- 数学・算数
- 合成確率の計算方法について
合成確率の計算方法について質問です。 合成確率の計算式で (分母A×分母B)÷(分母A+分母B)=合成確率 というものがあり、 総回転数が2000G、BIGが7回、REGが4回の場合、 (285×500)÷(285+500)=181.5 と求めることができますが、 総回転数が2000G、BIGが7回、REGが0回の場合、 (285×0)÷(285+0)= 0 (?) となり正確な数値が算出できません。 上記、計算式を使ってうまく計算する方法はあるのでしょうか? すいませんが、よろしくお願いいたします。
- ベストアンサー
- パチンコ・スロット
- 混合ガスの密度の計算
ガス状のLPガス、プロパン50wt%、ブタン50wt%の標準状態における密度はおよそ何kg/m3か?という問題ですが、単位質量1kgから計算すると2.2kg/m3ですが、1m3(1000l)から計算すると2.27kg/m3になります。どちらの計算方法が正しいのでしょうか? 1000l÷22.4l×44g×0.5=982.14 1000l÷22.4l×58g×0.5=1294.64 計2276.78g=2.27kg 低学歴ですので、申し訳ございません、よろしくお願いいたします。
- ベストアンサー
- 数学・算数
- 財務会計論CF計算書の法人税等について
財務会計論のCF計算書の直接法について分からない箇所があるのですが、 問題文で 未払法人税等のBS ・期首1200 ・期末(?) PLが (?) という状態で、問題文に「法人税等の中間納付は行っていない」と書かれている場合、 回答では、 ^^^^^^^^^^^^^^^^^^^^ ・営業活動によるキャッシュフロー ~~ 小計 ~~ 法人税等の支払額△1200 ^^^^^^^^^^^^^^^^^^^^ となっているのですが、なぜ期末が(?)でPLも(?)の状態で、 法人税等の支払額△1200と分かるのでしょうか? 「法人税等の中間納付は行っていない」状態とはどういう状態なのでしょうか? よろしくお願いします。
- ベストアンサー
- 公認会計士
- プッシュダウンオートマトンが!
プッシュダウンオートマトンの問題がわからないんですが、基本中の基本過ぎて参考書に載っていません(><) もしよかったら軽くヒントのようなものを出していただけないでしょうか?? L={aのn+1乗bのn乗|nZ|} を受理するプッシュダウンオートマトンを書け これはn+1の1ぶん補助テープがあまってしまうのでしょうか?? なにがなんだかさっぱりです↓
- 締切済み
- 科学