正規表現「(a|b)*a?」に対応するNFA遷移図、DFA遷移表、遷移図の作成方法について解説します。この正規表現に対応する有限オートマトンを求める際、ε遷移をどのように扱うかがポイントです。この記事では、まずNFA（非決定性有限オートマトン）の遷移図を作成し、次にそれをDFA（決定性有限オートマトン）に変換する方法を説明します。
正規表現 (a|b)*a? の理解
まず、正規表現「(a|b)*a?」を理解することが大切です。この正規表現は、次のような意味を持っています。
- (a|b)* は「a または b が任意回数繰り返される」という意味。
- a? は「a が0回または1回現れる」という意味。
この正規表現に従う文字列は、空文字列、a、b、ab、ba、aab、abb など様々な形になります。
NFA（非決定性有限オートマトン）の作成
NFAは、状態遷移において複数の遷移先が存在する可能性があるオートマトンです。まずは、この正規表現に対応するNFAの遷移図を作成します。
まず、(a|b)*の部分からNFAを作成します。この部分は、aまたはbを任意回数繰り返し処理できるため、状態遷移にはε（空遷移）を使います。
次に、a?の部分に対応する遷移を加えます。a?は「aが0回または1回現れる」と解釈し、aに対して1回の遷移を用意します。
DFA（決定性有限オートマトン）への変換
NFAからDFAに変換する際には、NFAの状態の組み合わせを一つの状態としてDFAの状態を作ります。これにより、DFAでは一つの状態に対して一意に遷移が決まるようになります。
DFAにおいて、状態遷移を明確に定義し、すべての入力文字に対して一意の遷移があることを確認します。例えば、aとbの入力に対して、それぞれどの状態に遷移するのかを明示的に書き出します。
具体的なNFA遷移図とDFA遷移表の作成
次に、具体的なNFA遷移図とDFA遷移表を示します。
NFA遷移図
1. 初期状態S0から、aまたはbに対して状態S1へ遷移。
2. 状態S1からaまたはbに対して状態S1へ戻る。
3. 状態S1から、aに対して状態S2（最終状態）へ遷移。
このようにしてNFAの遷移図を作成します。
DFA遷移表
| 状態 | a | b |
|---|---|---|
| S0 | S1 | S1 |
| S1 | S2 | S1 |
| S2 | S2 | S2 |
まとめ
正規表現「(a|b)*a?」に対応するNFA遷移図とDFA遷移表の作成方法を解説しました。まず、NFAではε遷移を使用して状態を遷移させ、次にそれをDFAに変換して一意の遷移を定義しました。具体的な遷移図と遷移表を作成することで、理解を深めることができます。
コメント