Automata-theory-ardens-theorem

アーデンの定理

有限オートマトンの正規表現を見つけるために、正規表現のプロパティとともにアーデンの定理を使用します。

*_Statement_* -

*P* と *Q* を2つの正規表現とします。

*P* にヌル文字列が含まれていない場合、 *R = Q + RP* には *R = QP* *という一意のソリューションがあります。

証明-

R = Q +（Q + RP）P [値R = Q + RPを入れた後]

Q + QP + RPP

私たちは R の値を繰り返し再帰的に配置すると、次の式が得られます-

R = Q + QP + QP ^ 2 ^ + QP ^ 3 ^…..

R = Q（ε+ P + P ^ 2 ^ + P ^ 3 ^ +…。 )

R = QP [P は（ε+ P + P2 + P3 +…。）を表すため]

したがって、証明した。

アーデンの定理を適用するための仮定

• 遷移図にNULL遷移を含めることはできません
• 初期状態は1つだけでなければなりません

方法

• ステップ1 *-初期状態がq〜1〜のn個の状態を持つDFAのすべての状態について、次の形式で方程式を作成します。

q〜1〜= q〜1〜R〜11〜+ q〜2〜R〜21〜… q〜n〜R〜n1〜+ε

q〜2〜= q〜1〜R〜12〜+ q〜2〜R〜22〜… q〜n〜R〜n2〜

…………………………

…………………………

…………………………

…………………………

q〜n〜= q〜1〜R〜1n〜+ q〜2〜R〜2n〜… q〜n〜R〜nn〜

• R〜ij〜は、 q〜i〜から q〜j〜までのエッジのラベルのセットを表し、そのようなエッジが存在しない場合は、 R〜ij〜=∅*

ステップ2 *-これらの方程式を解いて、 R〜ij〜*に関して最終状態の方程式を取得します。

問題

以下に示すオートマトンに対応する正規表現を構築します-

有限オートマトン

ソリューション-

ここで、初期状態と最終状態は* q〜1〜*です。

3つの状態q1、q2、およびq3の方程式は次のとおりです-

q〜1〜= q〜1〜a + q〜3〜a +ε（ε移動はq1が初期状態であるためです0

q〜2〜= q〜1〜b + q〜2〜b + q〜3〜b

q〜3〜= q〜2〜a

今、私たちはこれらの3つの方程式を解きます-

q〜2〜= q〜1〜b + q〜2〜b + q〜3〜b

q〜1〜b（b + ab）*（アーデンの定理の適用）

q〜1〜= q〜1〜a + q〜3〜a +ε

（a + b（b + ab）* aa）*

したがって、正規表現は（a + b（b + ab）* aa）*です。

問題

以下に示すオートマトンに対応する正規表現を構築します-

Finite Automata1

ソリューション-

ここで、初期状態はq〜1〜で、最終状態はq〜2〜です

今、我々は方程式を書き留めます-

q〜1〜= q〜1〜0 +ε

q〜2〜= q〜1〜1 + q〜2〜0

q〜3〜= q〜2〜1 + q〜3〜0 + q〜3〜1

今、私たちはこれらの3つの方程式を解きます-

q〜1〜=ε0 *[As、εR= R]

したがって、q〜1〜= 0*

q〜2〜= 0 *1 + q〜2〜0

したがって、q〜2〜= 0* 1（0） *[アーデンの定理による]

したがって、正規表現は0* 10 *です。