Twierdzenie Ardena
Aby znaleźć wyrażenie regularne automatu skończonego, używamy twierdzenia Ardena wraz z właściwościami wyrażeń regularnych.
Statement -
Pozwolić P i Q być dwoma wyrażeniami regularnymi.
Jeśli P nie zawiera pustego łańcucha R = Q + RP ma unikalne rozwiązanie R = QP*
Proof -
R = Q + (Q + RP) P [Po wprowadzeniu wartości R = Q + RP]
= Q + QP + RPP
Kiedy podamy wartość R rekurencyjnie raz po raz otrzymujemy następujące równanie -
R = Q + QP + QP 2 + QP 3 … ..
R = Q (ε + P + P 2 + P 3 +….)
R = QP * [Jak P * oznacza (ε + P + P2 + P3 +….)]
Stąd udowodniono.
Założenia do stosowania twierdzenia Ardena
- Diagram przejść nie może mieć przejść NULL
- Musi mieć tylko jeden stan początkowy
metoda
Step 1- Utwórz równania jako następującą postać dla wszystkich stanów DFA mających n stanów ze stanem początkowym q 1 .
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
Rij reprezentuje zestaw etykiet krawędzi z qi do qjjeśli nie ma takiej krawędzi, to Rij = ∅
Step 2 - Rozwiąż te równania, aby otrzymać równanie stanu końcowego w postaci Rij
Problem
Skonstruuj wyrażenie regularne odpowiadające automatom podanym poniżej -
Solution -
Tutaj jest stan początkowy i stan końcowy q1.
Równania dla trzech stanów q1, q2 i q3 są następujące -
q 1 = q 1 a + q 3 a + ε (ε ruch jest taki, że q1 jest stanem początkowym 0
q 2 = q 1 b + q 2 b + q 3 b
q 3 = q 2 a
Teraz rozwiążemy te trzy równania -
q 2 = q 1 b + q 2 b + q 3 b
= q 1 b + q 2 b + (q 2 a) b (Wartość zastępująca q 3 )
= q 1 b + q 2 (b + ab)
= q 1 b (b + ab) * (stosując twierdzenie Ardena)
q 1 = q 1 a + q 3 a + ε
= q 1 a + q 2 aa + ε (wartość zastępująca q 3 )
= q 1 a + q 1 b (b + ab *) aa + ε (Wartość zastępująca q 2 )
= q 1 (a + b (b + ab) * aa) + ε
= ε (a + b (b + ab) * aa) *
= (a + b (b + ab) * aa) *
Stąd wyrażenie regularne to (a + b (b + ab) * aa) *.
Problem
Skonstruuj wyrażenie regularne odpowiadające automatom podanym poniżej -
Solution -
Tutaj stan początkowy to q 1, a stan końcowy to q 2
Teraz zapisujemy równania -
q 1 = q 1 0 + ε
q 2 = q 1 1 + q 2 0
q 3 = q 2 1 + q 3 0 + q 3 1
Teraz rozwiążemy te trzy równania -
q 1 = ε0 * [As, εR = R]
Zatem q 1 = 0 *
q 2 = 0 * 1 + q 2 0
Zatem q 2 = 0 * 1 (0) * [według twierdzenia Ardena]
Dlatego wyrażenie regularne to 0 * 10 *.