ソフトウェア

次の正規表現 `(ab)*c` を認識する有限オートマトン（DFA）において、文字列 "ababc" を入力したとき、受理されるか否かと、その理由として正しいものはどれか。

ア.受理されない。正規表現 (ab)* はabの繰り返しのみ許可し、cは含めない

イ.受理される。"ab"を2回繰り返し最後にcが来るので正規表現に一致する正解

ウ.受理される。ただしDFAでは正規表現の検証は不可能

エ.受理されない。"ababc"は長すぎてDFAが処理できない

解説

正規表現とDFAは「同じ言語を表現する2つの顔」。`(ab)*c`は「abを0回以上繰り返してcで終わる」文字列のパターン。ababcはab×2＋c！

なぜイが正解か

正規表現 (ab)*c の意味: "ab"を0回以上繰り返した後に"c"が続く文字列。"ababc"を分解: "ab"(1回目) + "ab"(2回目) + "c" → (ab)²c → パターンに一致。DFAで追跡: 状態q0→a→q1→b→q0→a→q1→b→q0→c→q_accept(受理状態)。正しく受理される。

なぜアは間違いか

(ab)*cのcは必須の終端文字。cが末尾にくることで受理される。cを「含めない」という解釈は誤り。

なぜウは間違いか

DFAは正規言語を認識する計算モデル。正規表現と等価な表現力を持ち、正規表現で定義された言語は必ずDFAで認識可能。「DFAでは正規表現の検証が不可能」は誤り。

なぜエは間違いか

DFAの処理能力は入力長に制限がない（理論的には無限長も扱える）。"ababc"は有限長であり問題なく処理できる。

出典: AI生成問題（学習用）

← 前の問題

資源割当グラフによるデッドロック検出に関して、次の状況を考える。プロセスP1はR1を保持しR2を要求、プロセスP2はR2を保持しR3を要求、プロセスP3はR3を保持しR1を要求している。この状況の判定として正しいものはどれか。

次の問題 →

プッシュダウンオートマトン（PDA）に関する説明として正しいものはどれか。

ソフトウェアの問題を解くこの分野の問題一覧を見る