🎓 大学定期試験・院試対策
オートマトン・形式言語・計算理論過去問・一問一答
- 収録問題
- 50問
- カテゴリ
- 4分野
あなたの達成率
完了率 0%0 / 50問 正解済み
収録問題一覧
✓ 正解済み ✕ 前回不正解
有限オートマトン（DFA/NFA）と正規表現19問
- cs-automata-001・易決定性有限オートマトン（DFA）が受理する言語のクラスと、非決定性有限オートマトン（NFA）が受理する言語のクラスの関係として、正しいものはどれか。
- cs-automata-002・標準状態数が n の NFA を部分集合構成法で DFA に変換するとき、得られる DFA の状態数の上限はどれか。
- cs-automata-003・易アルファベット {a, b} 上の正規表現 (ab)*a が表す言語に含まれる文字列はどれか。
- cs-automata-004・標準アルファベット {a, b} 上で、「a の個数が偶数で、かつ b の個数が奇数」である文字列だけを受理する DFA の最小の状態数はいくつか。
- cs-automata-005・標準DFA の最小化において、2つの状態 p と q を1つの状態にまとめてよい条件として、適切なものはどれか。
- cs-automata-006・標準空動作を含む NFA で、状態 q0 から q1 へ、q1 から q3 へそれぞれ ε遷移があり、q0 から q2 へは記号 a による遷移だけがある。ほかに ε遷移はない。q0 の ε閉包（ε遷移だけでたどり着ける状態の集合）はどれか。
- cs-automata-007・標準アルファベット {a, b} 上の正規表現のうち、(a|b)* と同じ言語を表すものはどれか。
- cs-automata-008・難アルファベット {a, b} 上の言語のうち、正規言語でないものはどれか。
- cs-automata-009・標準正規言語のクラスの性質として、正しいものはどれか。
- cs-automata-010・標準状態 p（開始状態）、q、r（受理状態）からなる DFA の遷移が、p では a で q・b で p、q では a で q・b で r、r では a で q・b で p である。この DFA が受理する文字列はどれか。
- cs-automata-011・標準非終端記号 S, A、終端記号 a, b、開始記号 S からなる正規文法で、生成規則が S → aS、S → bA、A → a のとき、この文法が生成する言語を表す正規表現はどれか。
- cs-automata-013・標準状態の集合を Q、入力記号の集合を Σ、空動作を ε とするとき、空動作を含む非決定性有限オートマトンの遷移関数 δ の型として適切なものはどれか。ここで、 は Q の部分集合全体の集合を表す。
- cs-automata-014・標準クリーネの定理の内容として、適切なものはどれか。
- cs-automata-015・難アルファベット {a, b} 上で、「末尾から2番目の文字が a である」文字列だけを受理する DFA の最小の状態数はいくつか。
- cs-automata-016・標準状態数がそれぞれ m と n の2つの DFA があるとき、両方が受理する文字列（共通部分）だけを受理する DFA を直積構成で作ると、状態数はいくつになるか。
- cs-automata-017・易アルファベット {a, b} 上の正規表現 a* が表す言語について、正しいものはどれか。
- cs-automata-018・易正規表現 (0|1)*00 が表す言語に含まれる2進列はどれか。
- cs-automata-019・標準正規表現から空動作を含む NFA を構成する方法（トンプソンの構成法）で、連接 に対応する NFA の作り方として、適切なものはどれか。
- cs-automata-020・易アルファベット {a, b} 上で、「a が3個以上連続する部分を含む」文字列だけを受理する DFA がある。この DFA が受理しない文字列はどれか。
文脈自由文法とプッシュダウンオートマトン16問
- cs-automata-012・易計算モデルと、それがもつ補助記憶の組合せとして、正しいものはどれか。
- cs-automata-021・易チョムスキー階層における言語のクラスの包含関係として、正しいものはどれか。ここで、⊊ は真部分集合を表す。
- cs-automata-022・標準文脈自由文法の生成規則の形として、適切なものはどれか。ここで、A は非終端記号、α, β, γ は終端記号と非終端記号からなる記号列とする。
- cs-automata-023・易生成規則 S → aSb、S → ε（ε は空列）をもつ文脈自由文法が生成する言語はどれか。
- cs-automata-024・標準生成規則 S → aSc、S → T、T → bT、T → ε（ε は空列）をもち、開始記号が S である文法が生成する言語はどれか。
- cs-automata-025・標準生成規則 S → SS、S → (S)、S → ε（ε は空列）をもつ文法から導出できる記号列はどれか。
- cs-automata-026・標準文脈自由文法が曖昧であるとは、どういうことか。
- cs-automata-027・標準非決定性プッシュダウンオートマトンが受理する言語のクラスと等しいものはどれか。
- cs-automata-028・難決定性プッシュダウンオートマトン（DPDA）と非決定性プッシュダウンオートマトン（NPDA）について、正しい記述はどれか。
- cs-automata-029・標準チョムスキー標準形の文脈自由文法の生成規則の形として、正しい組合せはどれか。ここで、A, B, C は非終端記号、a は終端記号とし、空列の扱いは考えない。
- cs-automata-030・難文脈自由言語のクラスの性質について、正しい記述はどれか。
- cs-automata-031・難文脈自由言語ではないことが知られている言語はどれか。
- cs-automata-032・難チョムスキー標準形の文脈自由文法について、長さ n の記号列がその文法から導出できるかを判定する CYK 法の時間計算量はどれか。ここで、文法の大きさは定数とみなす。
- cs-automata-033・難プッシュダウンオートマトンの受理の方式には「最終状態で受理」と「空スタックで受理」がある。非決定性プッシュダウンオートマトンについて、両者の関係として正しいものはどれか。
- cs-automata-034・易生成規則 S → aSb、S → ab をもつ文法で、開始記号 S から記号列 aaaabbbb を導出するのに必要な規則の適用回数はいくつか。
- cs-automata-035・易文脈自由文法の構文木（導出木）について、正しい記述はどれか。
チューリングマシンと決定可能性8問
- cs-automata-036・易チューリング機械の構成要素として、適切な組合せはどれか。
- cs-automata-037・標準停止性問題についての記述として、正しいものはどれか。
- cs-automata-038・標準チャーチ＝チューリングのテーゼの内容として、適切なものはどれか。
- cs-automata-039・標準万能チューリング機械の説明として、適切なものはどれか。
- cs-automata-040・難チューリング機械 M と入力 w の組 (M, w) のうち、M が w に対して停止するもの全体の集合を H とする。H の性質として、正しいものはどれか。
- cs-automata-041・難文脈依存文法が生成する言語のクラスと、受理する言語のクラスが等しい計算モデルはどれか。
- cs-automata-042・標準次の問題のうち、決定可能である（必ず停止して正しく判定するアルゴリズムが存在する）ものはどれか。
- cs-automata-043・難ある問題 X が決定不能であることを、停止性問題を用いて示す方法として、適切なものはどれか。
計算複雑性（P・NP問題）7問
- cs-automata-044・易計算複雑性の理論におけるクラス P の説明として、適切なものはどれか。
- cs-automata-045・標準クラス NP に属する判定問題の性質として、適切なものはどれか。
- cs-automata-046・標準NP 完全問題の定義として、適切なものはどれか。
- cs-automata-047・標準クック・レビンの定理によって、最初に NP 完全であることが示された問題はどれか。
- cs-automata-048・標準ある NP 完全問題に対して、多項式時間のアルゴリズムが見つかったとすると、どのような結論が得られるか。
- cs-automata-049・難次の判定問題のうち、多項式時間で解けることが知られている（クラス P に属する）ものはどれか。
- cs-automata-050・難NP 困難（NP-hard）と NP 完全の関係について、正しい記述はどれか。