平成27年度 III-28

解説

この問題で問われていること

状態遷移図(ε遷移付きNFA)から、受理される文字列の集合を、正規表現に変換する問題。

解き方

① 選択肢の正規表現は、図で受理される・されない文字列を当てて消していく
② 空列は受理(初期→ε→受理)→ ④×。「bb」は受理しない(bの後は必ずa)→ ①×。「aba」は a の後に受理状態から初期状態へ戻り ba を読んで受理 → aとbaを混ぜられない③⑤×
残るのは (a|ba)*
③ ②

正解が正しい理由

初期状態をS、受理状態をFとする。上側の経路は、Sからε遷移で、次の状態に進み、aで別の状態に遷移し、その状態から、前の状態へε遷移で戻るか、Fへε遷移で進む。よってa1回以上の繰り返し(a+)を、受理する。下側は、Sからεで直接Fに行けるので、空列も受理する。下の経路は、Sからbで状態Cに進み、Cからaを読んでFに進むか、aで別の状態Dに進み、Dからbを読んでCに戻る。よって、b(ab)*aで、これは(ba)(ba)*=(ba)+と同じである。さらに、Fから、Sへのε遷移があるので、これらの全体を、何回でも繰り返せる。したがって、(ε|a+|(ba)+)*=(a|ba)*で、②が正しい。

各選択肢について

• ① (a|b)*は、bだけが連続する文字列(bb など)も受理するが、この図では、bの後には必ずaが続くので、誤り。
• ② aと、baの組合せを任意回繰り返した文字列を受理する。これが正答。
• ③ a*|(ba)*は、aのみの繰返しか、baのみの繰返しのどちらか一方しか受理しない。Fからのε遷移により、aとbaを混ぜた文字列(例: aba)も受理されるので、誤り。
• ④ a*ba(ba)*は、必ずbaを含むことを要求するため、空列やaのみの文字列を受理できず、誤り。
• ⑤ a*|((ba)(ba)*)は、③と同様に、aとbaを混ぜた文字列を受理できず、誤り。

覚えるべきポイント

ε遷移付きNFAから正規表現を作るときは、(1)ループになっている部分を、*や+で表す、(2)並列の経路を|で表す、(3)受理状態から初期状態へ戻るε遷移は、全体の繰返しを意味する、と整理する。