科目 大学院の科目


(大学院)計算論('10)




平成23年1月

択一式か記述式か :    択一式

設問数 :    10

出題元 :    テキスト中心

持ち込み可能か :    持ち込み可




コメント :
計算論('10) (10問、テキスト中心、持込可、大学院科目)
1.記号列の部分列、接頭語について
2.正規表現(a(ab+c))の表す集合は?
3.定義された文法規則の用い方として正しいものを選べ。
4.定義されたオートマトンに文字列を入力した場合の最終状態を選べ。
5.定義された非決定性オートマトンに文字列を入力した場合の最後にとりうる状態の集合を選べ。
6.定義された2方向オートマトンについてある状態から計算を進めた場合の最終状態を選べ。
7.定義されたε‐動作を含むオートマトンで初期状態からε‐動作を何回か繰り返すことでとりうる状態の集合を選べ。
8.問7のε‐動作を含むオートマトンに文字列を入力した場合の最後にとりうる状態の集合を選べ。
9.定義されたチューリング機械について、ある時点表示の1ステップ後の時点表示を選べ。
10.問9のチューリング機械の文字列を入力した場合に、計算終了時にテープに書かれている記号列を選べ。
 
授業で説明されるオートマトン等の計算規則を理解しておけば
特に難しい問題はありませんでした。