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 *.