Mi è stato assegnato un incarico per simulare un NFA in Java. Ora la seguente espressione regolare che devo simulare un NFA per èSimulazione NFA in Java
ab*((b|d)|c*)
Penso di avere troppe e-simboli. Mi stavo chiedendo se la seguente immagine qui sotto è corretta.
Il grafico NFA è corretta. Corrisponde alla regex ab*((b|d)|c*) e nient'altro. Tuttavia, potrebbe essere molto più semplice, ad es. in questo modo:
Non penso che sia completamente corretto, la parte ramificata '((b | d) | c *)' è due rami, non tre, è o (b | d) o c *, quindi dal tuo 'b' nodo non sarebbe più accurato rappresentarlo come un percorso completamente separato che poi si ramifica in 'b' o' d'? –
Sono sicuro che quello sopra non stia usando la costruzione Thompson. È più breve ma mi è stato dato uno stile di come farlo dal mio docente. – unleashed
@unleashed Direi che Thompson è un algoritmo (una procedura) per creare un NFA, non un tipo di NFA. Puoi vedere il mio NFA come qualcosa creato con Thompson e quindi ottimizzato. (A proposito: la domanda era se il tuo NFA è equivalente alla tua espressione regolare. Nulla su Thomspon :-)) –
nodi 10, 11, 12 e 13 potrebbe probabilmente essere condensati in appena due nodi? –
Questo è ciò che inizialmente pensavo, ma il docente vuole che lo stile utilizzi in precedenza per ripetere e usare la costruzione di Thompson per creare l'NFA. Sono piuttosto dubbioso per la transizione da 2 a 3 e, per la transizione da 3 a 4 e per la transizione da 4 a 5 o da 4 a 7 e. – unleashed
Bene, il 2-3 potrebbe essere ridotto, in caso di 'b *' risultante in non 'b's si avrebbe una transizione' e' da 1-2. A parte questo, penso che il resto sembra appropriato. In definitiva il risultato finale è lo stesso, solo un nodo in meno. –