Costruzione di una FA da RE

Possiamo usare la costruzione di Thompson per scoprire un automa finito da un'espressione regolare. Ridurremo l'espressione regolare in espressioni regolari più piccole e le convertiremo in NFA e infine in DFA.

Alcune espressioni RA di base sono le seguenti:

Case 1 - Per un'espressione regolare 'a', possiamo costruire il seguente FA -

Case 2 - Per un'espressione regolare 'ab', possiamo costruire il seguente FA -

Case 3 - Per un'espressione regolare (a + b), possiamo costruire il seguente FA -

Case 4 - Per un'espressione regolare (a + b) *, possiamo costruire il seguente FA -

Metodo

Step 1 Costruisci un NFA con mosse Null dall'espressione regolare data.

Step 2 Rimuovi la transizione nulla dall'NFA e convertila nel suo equivalente DFA.

Problem

Converti il ​​seguente RA nel suo equivalente DFA - 1 (0 + 1) * 0

Solution

Concateneremo tre espressioni "1", "(0 + 1) *" e "0"

Ora rimuoveremo il file εtransizioni. Dopo aver rimosso il fileε transizioni dall'NDFA, otteniamo quanto segue:

È un NDFA corrispondente a RE - 1 (0 + 1) * 0. Se vuoi convertirlo in un DFA, applica semplicemente il metodo di conversione da NDFA a DFA discusso nel Capitolo 1.

Automi finiti con mosse nulle (NFA-ε)

Un automa finito con mosse nulle (FA-ε) transita non solo dopo aver dato input dal set di alfabeto, ma anche senza alcun simbolo di input. Questa transizione senza input è chiamata anull move.

Un NFA-ε è formalmente rappresentato da una 5-tupla (Q, ∑, δ, q 0 , F), composta da

  • Q - un insieme finito di stati

  • ∑ - un insieme finito di simboli di input

  • δ- una funzione di transizione δ: Q × (∑ ∪ {ε}) → 2 Q

  • q0- uno stato iniziale q 0 ∈ Q

  • F - un insieme di stati finali di Q (F⊆Q).

Quanto sopra (FA-ε) accetta un set di stringhe - {0, 1, 01}

Rimozione delle mosse nulle dagli automi finiti

Se in un NDFA è presente uno spostamento move tra il vertice X e il vertice Y, possiamo rimuoverlo utilizzando i seguenti passaggi:

  • Trova tutti i bordi in uscita da Y.
  • Copia tutti questi bordi a partire da X senza modificare le etichette dei bordi.
  • Se X è uno stato iniziale, rendi anche Y uno stato iniziale.
  • Se Y è uno stato finale, rendi anche X uno stato finale.

Problem

Converti il ​​seguente NFA-ε in NFA senza spostamento Null.

Solution

Step 1 -

Qui la transizione ε è tra q1 e q2, quindi lascia q1 è X e qf è Y.

Qui gli archi in uscita da q f sta a q f per gli ingressi 0 e 1.

Step 2 -

Ora copieremo tutti questi bordi da q 1 senza cambiare i bordi da q f e otterremo il seguente FA -

Step 3 -

Qui q 1 è uno stato iniziale, quindi rendiamo anche q f uno stato iniziale.

Quindi la FA diventa -

Step 4 -

Qui q f è uno stato finale, quindi rendiamo anche q 1 uno stato finale.

Quindi la FA diventa -