Teorema di Arden
Per trovare un'espressione regolare di un automa finito, usiamo il teorema di Arden insieme alle proprietà delle espressioni regolari.
Statement -
Permettere P e Q essere due espressioni regolari.
Se P non contiene una stringa nulla, quindi R = Q + RP ha una soluzione unica che è R = QP*
Proof -
R = Q + (Q + RP) P [Dopo aver inserito il valore R = Q + RP]
= Q + QP + RPP
Quando mettiamo il valore di R ripetutamente in modo ricorsivo, otteniamo la seguente equazione:
R = Q + QP + QP 2 + QP 3 … ..
R = Q (ε + P + P 2 + P 3 +….)
R = QP * [Come P * rappresenta (ε + P + P2 + P3 +….)]
Quindi, dimostrato.
Presupposti per l'applicazione del teorema di Arden
- Il diagramma di transizione non deve avere transizioni NULL
- Deve avere un solo stato iniziale
Metodo
Step 1- Creare equazioni nel seguente formato per tutti gli stati del DFA aventi n stati con stato iniziale 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 rappresenta l'insieme di etichette di bordi da qi per qj, se non esiste un tale margine, allora Rij = ∅
Step 2 - Risolvi queste equazioni per ottenere l'equazione per lo stato finale in termini di Rij
Problem
Costruisci un'espressione regolare corrispondente agli automi forniti di seguito -
Solution -
Qui lo stato iniziale e lo stato finale sono q1.
Le equazioni per i tre stati q1, q2 e q3 sono le seguenti:
q 1 = q 1 a + q 3 a + ε (ε spostare è perché q1 è lo stato iniziale0
q 2 = q 1 b + q 2 b + q 3 b
q 3 = q 2 a
Ora risolveremo queste tre equazioni:
q 2 = q 1 b + q 2 b + q 3 b
= q 1 b + q 2 b + (q 2 a) b (Sostituendo il valore di q 3 )
= q 1 b + q 2 (b + ab)
= q 1 b (b + ab) * (Applicando il teorema di Arden)
q 1 = q 1 a + q 3 a + ε
= q 1 a + q 2 aa + ε (Sostituendo il valore di q 3 )
= q 1 a + q 1 b (b + ab *) aa + ε (Sostituendo il valore di q 2 )
= q 1 (a + b (b + ab) * aa) + ε
= ε (a + b (b + ab) * aa) *
= (a + b (b + ab) * aa) *
Quindi, l'espressione regolare è (a + b (b + ab) * aa) *.
Problem
Costruisci un'espressione regolare corrispondente agli automi forniti di seguito -
Solution -
Qui lo stato iniziale è q 1 e lo stato finale è q 2
Ora scriviamo le equazioni -
q 1 = q 1 0 + ε
q 2 = q 1 1 + q 2 0
q 3 = q 2 1 + q 3 0 + q 3 1
Ora risolveremo queste tre equazioni:
q 1 = ε0 * [As, εR = R]
Quindi, q 1 = 0 *
q 2 = 0 * 1 + q 2 0
Quindi, q 2 = 0 * 1 (0) * [per il teorema di Arden]
Quindi, l'espressione regolare è 0 * 10 *.