文脈自由文法についての質問
- 文脈自由文法について勉強している中で、答えがわからない問題に困っています。
- 質問の内容は、与えられた文脈自由文法が10進数以外の数値も受容してしまう例を示し、その欠陥をなくすための規則変更、8進数の受容方法についてです。
- 解答を教えていただける方がいらっしゃいましたら、お願いいたします。
- ベストアンサー
文脈自由文法についての質問です
文脈自由文法についての質問です 最近、文脈自由文法について勉強しているんですがテキストの問題の中に 答えがわからない問題があるので困ってます。 その問題が下に示してあるものです。 Q.次の文脈自由文法G=(V,T,S,P)は、本来は10進数の数値を受容する目的で作られたものであるが、 この文脈自由文法には欠陥があり、10進数として読めるもの以外も受容してしまう。 <S>を開始記号、<N>、<M>を非終端記号とする。 規則P: <s> → <N> <N> → <M><N> | <M> | <N>.<N> <M> → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 1.10進数以外の数値でも受容してしまう例を1つ示せ。 2.1で示した例のように、10進の数値以外を受容してしまうような欠陥をなくすためには、 どのように文脈自由文法をの規則を変更すればよいか、変更後の規則をすべて示せ。 なお、非終端記号や終端記号は必要に応じて追加して良い。 3.2で変更した文脈自由文法に対し、8進数を受容するにはどのように文脈自由文法の規則を 変更すればよいかを示せ この問題を解ける方がいましたら教えて頂きたいのでよろしくお願いします。 長文失礼しました。
- takkuman03
- お礼率0% (0/9)
- 数学・算数
- 回答数2
- ありがとう数0
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
１ 1.2.3 のような小数点が２個以上ある場合。 ２ <N>.<N>の箇所が間違いです。 小数点を含まない場合の記号を別に作る必要があります。 ３ 8と9の数字を除くだけです。
その他の回答 (1)
関連するQ&A
- 文脈自由文法についての質問です
文脈自由文法についての質問です 最近、文脈自由文法について勉強しているんですがテキストの問題の中に 解き方がわからない問題があるので困ってます。 その問題が下に示してあるものです。 Q.次の文脈自由文法G=(V,T,S,P)は、本来は10進数の数値を受容する目的で作られたものであるが、 この文脈自由文法には欠陥があり、10進数として読めるもの以外も受容してしまう。 <S>を開始記号、<N>、<M>を非終端記号とする。 規則P: <s> → <N> <N> → <M><N> | <M> | <N>.<N> <M> → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 1.10進数以外の数値でも受容してしまう例を1つ示せ。 2.1で示した例のように、10進の数値以外を受容してしまうような欠陥をなくすためには、 どのように文脈自由文法をの規則を変更すればよいか、変更後の規則をすべて示せ。 なお、非終端記号や終端記号は必要に応じて追加して良い。 3.2で変更した文脈自由文法に対し、8進数を受容するにはどのように文脈自由文法の規則を 変更すればよいかを示せ この問題を解ける方がいましたら教えて頂きたいのでよろしくお願いします。 長文失礼しました。
- ベストアンサー
- その他（プログラミング・開発）
- 文脈自由文法をチョムスキー標準形に変換
大学の数学で分からない問題があります。 どなたか教えていただけないでしょうか？ １．次の規則を持つ文脈自由文法をチョムスキー標準形に変換せよ。 (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 問題は以上です。長くなってしまい申し訳ありません。 また、学校で何やっていたんだとお怒りの方もいらっしゃるかと思いますが、何卒よろしくお願いします。
- ベストアンサー
- 数学・算数
- 次の生成文法を考える。なお、Sは開発記号、S,A,B は非終端記号，ァ
次の生成文法を考える。なお、Sは開発記号、S,A,B は非終端記号，ァ、bは終端記号とする。 文字列 aabababaa が生成される最左導出を求める
- 締切済み
- 数学・算数
- 言語理論の文脈自由言語について
「オートマトン 言語理論 計算論Ｉ」という本（教科書）を読んでいます。 この本には演習問題がついているのですが、本を読んだだけでは解法が分らない上、 答えがついてないため、解けない問題が多く困っています。 （連休明けに試験があり、その範囲なんです。） ある言語が文脈自由型ででないことを証明したいのですが、 反復補題（パンピングレンマ）を用いて背理法によるのだろうと思うのですが、 どのように仮定するかの方針が立たないのです。 具体的には次のような問題に対し、「…」のような仮定をしてみました。 ａ）｛ａ＾ｉ ｂ＾ｊ ｃ＾ｋ ｜ ｉ＜ｊ＜ｋ｝ 「ｚ＝ａ＾ｎ ｂ＾（ｎ＋ｌ） ｃ＾（ｎ＋ｍ） （但し、ｍ＞ｌ＞０）」 しかし、下記のように背理法による矛盾が示せなかったのです。 どこで間違ったのかは分らないので、間違った個所を指摘していただきたいのです。 よろしくお願いします。 「言語を文脈自由言語と仮定する。 ｎをパンピングレンマの性質を持つ整数とし、 ｚ＝ａ＾ｎ ｂ＾（ｎ＋ｌ） ｃ＾（ｎ＋ｍ） （但し、ｍ＞ｌ＞０）とすると、 ｚ∈Ｌ かつ ｜ｚ｜≧ｎ が成立する。 したがって、パンピングレンマから ｚ＝ｕ ｖ ｗ ｘ ｙ （ｕｘ≠ε、｜ｖｗｘ｜≦ｎ） と表され、かつ ｕ ｖ＾ｉ ｗ ｘ＾ｉ ｙ ∈ Ｌ が成立する。 ｜ｖｗｙ｜≦ｎ なので、ｖｘがａとｃの両方を含むことはない。 ｖｘのパターンにより次の２つの場合を考える （ｉ）ｖｘが一種類の文字だけからなる場合 … （ｉｉ）ｖｘが２種類の文字からなる場合」 ここまで書いたところで、 ｖ＝ｂ、ｘ＝ｃ とすると、例えば、 ｕ＝ａ、ｗ＝ｂｂ、ｙ＝ｃｃｃ の場合を考えると、矛盾が導けないことに気付きました。
- ベストアンサー
- 科学
- 確率：条件付期待値
全く、条件付期待値というのでしょうか？そこが分かりません。もし宜しければ、ご教授ください。 問題： N(1)を2005年度における有効な規則の数とします。 M(1)を2005年度において有効な規則、且次の年も有効な規則の数とします。 よってN(2)=M(1)+A(2), A(2)は新しい規則です。 E[N(1)]=m, Var[N(1)]=s^2, 次の年に規則が有効になる確率はp. q=1-p M(1)とA(2)は独立で、A(2)～Poi(λ). N(1)=nとし、M(2)～(n,p). 上記のような問題がある場合、次のことを計算します。 (1)E[N(2)]=E[M(1)]+E[A(2)]=mp + λ (2)E[M(2)]=E[E[M(2)|N(1)]]=E[N(1) p] = pE[N(1)]=mp (3)Var[N(2)]=Var[M(2)]+Var[A(2)]=Var[M(2)]+λ (4)Var[M(2)|N(1)=n]=npq (5)E[M(2)^2|N(1)=n]=npq + (np)^2 (6)E[M(2)^2]=E[N(1)]pq + E[N(1)^2]p^2=mqp+(m^2+s^2)p^2 質問：この(2),(4),(6)が全く分かりません。宜しければ、少し詳しく教えてください。
- ベストアンサー
- 数学・算数
- ある言語クラス判定問題(正規言語?文脈自由言語?)
形式言語に関する以下の問題に悩んでおります。 問題: 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)ではない。理由はかくかくしかじか)でもありがたいですので、どうぞよろしくお願いいたします。
- 締切済み
- 数学・算数
- 統計学における自由度
統計を勉強し始めたものです。 統計学における自由度の定義がイマイチわかりません。 なるほど！、と思う説明に出会えないでいます。 よく自由度は「自由に動ける変数の数」だと教科書に書いてあるのですが 例えば、2標本問題(e.g.男女の身長)で標本平均の差の標本分布を求める際、男子の標本の大きさをm、女子の標本の大きさをnとした時（互いに独立）の自由度はm+n-2となることが理解できません。 この場合、 「男子の平均」ー「女子の平均」 の分布を考えるので自由度（自由に動ける変数の数）はm+n-1でもいい気がしてしまいます。 教科書には「2つの標本平均を使って偏差の平方和を計算するから、自由度が2失われる」と書いてあるのですがなかなかこの説明が頭に入りません。 勉強不足で申し訳ありませんが、自由度を定性的に理解できる説明を教えて下さい。 よろしくお願い致します。
- 締切済み
- 数学・算数
- ２自由度系の自由振動
２自由度系の自由振動の問題ですが、どのように考えれば良いのかわかりません。 どうかご教授ください。 長さlで質量mの一様な棒の右端に、質量mの球が付いています。 棒の両端は、バネ定数kのバネで地面とつながっています。 (1)ラグランジュの方程式を使用して運動方程式を立てよ。 (2)2つの固有振動数を求めよ。
- ベストアンサー
- 物理学
