基本情報技術者 2011年 春期 午前（科目A） 問04

有限オートマトンによる文字列検査【午前解説】

正解の理由

解法ステップ

1. 各選択肢の文字列を左端から1文字ずつ読む。△は空白とする。
2. 各文字を「空白／数字／符号／小数点／その他」の5種類に分類する。
3. 現在の状態と文字種から遷移表を参照して次状態を決める。
4. 次状態がeになった時点でその文字列は不合格と判定し、処理を中止する。
5. どの文字でもeにならなければ合格と判断する（本問では合格／不合格の2値判断）。

選択肢別の誤答解説

• ア: +0010
  • 遷移：a（初期）→'+'（符号）でc、'0'でc→b、その後は数字でbに留まる。eに到達しないため合格。
• イ: -1
  • 遷移：a→'-'（符号）でc、'1'でc→b。検査中にeに遷移しないため合格。
• ウ: 12.2
  • 遷移：a→'1'でb、'2'でb、'.'でb→d、最後の'2'でd→数字によりeに遷移。途中でeになったため不合格。
• エ: 9.△（末尾が空白）
  • 遷移：a→'9'でb、次に空白でb→aに戻る。eに到達しないため合格。

よくある誤解

• 「評価は最終状態のみを見る」と考える誤解：本問では途中でeになれば即不合格なので途中の遷移を必ず確認する必要があります。
• 「△を空文字（何もない）と解釈する」誤解：△は空白文字（スペース）を表します。空文字（長さ0）とは別扱いになる点に注意してください。
• 「小数点の後の数字は許されるはず」と考える誤解：表に従うとd（小数点後の状態）から数字へ遷移するとeになるため、この表では小数点直後に数字を続けると不合格になります。

補足コラム

trans = {
    'a': {'space':'a','digit':'b','sign':'c','dot':'d','other':'e'},
    'b': {'space':'a','digit':'b','sign':'e','dot':'d','other':'e'},
    'c': {'space':'e','digit':'b','sign':'e','dot':'d','other':'e'},
    'd': {'space':'a','digit':'e','sign':'e','dot':'e','other':'e'}
}
def char_type(ch):
    if ch == ' ':
        return 'space'
    if ch.isdigit():
        return 'digit'
    if ch in '+-':
        return 'sign'
    if ch == '.':
        return 'dot'
    return 'other'

def check(s):
    state = 'a'
    for ch in s:
        state = trans[state][char_type(ch)]
        if state == 'e':
            return False  # 不合格
    return True  # 合格

print(check("12.2"))  # False -> 不合格

FAQ