Costruire un automa a stati finiti

Come indicato nei commenti, arbitrary può includere 0 , quindi dovresti avere * invece di + nell'espressione regolare nei luoghi corrispondenti.

Dalla tua espressione regolare originale hai derivato correttamente un automa a stati finiti non deterministico (NFA). Per adattarlo al * menzionato sopra, devi solo eliminare gli stati 2 e 5 per avere di nuovo un NFA corrispondente.

La parte interessante della domanda d'esame è di derivare una macchina a stati finiti deterministica dal tuo NFA. Questo è meccanicamente possibile tramite un algoritmo denominato costruzione di powerset . Questo link dovrebbe darti abbastanza informazioni (e dovresti averlo imparato nelle tue lezioni sempre, vista la domanda d'esame!) Per sapere come ottenere da NFA a DFA.

Il DFA risultante è di solito troppo grande a causa del powerset degli stati, che è la ragione, perché normalmente si esegue una minimizzazione di DFA in seguito. Anche se per essere onesti, salterò la discussione visto che la domanda richiede solo un DFA, non un minimo DFA.

Non sono esperto ma ritengo che questa ipotesi sia corretta.

I am under the impression this is wrong because [A-Z] is a subgroup of [A-Za-z0-9] and a DFA cannot have the same symbol going from one state.

Sembra che tu abbia una buona conoscenza, ma la spellerò solo per essere accurata.

Di seguito sono riportati i passaggi per convertire l'NFA corrente in un DFA. Il primo passo consiste nel valutare dove esiste il non-determinismo in modo che il problema possa essere ulteriormente scomposto.

La suddivisione iniziale deve avvenire in base a una di queste due condizioni:

The user name can be either the employee’s name followed by a colon and then the department name

Ie. si incontra un nome 'employee_name'

a string of one or more alphanumeric letters consisting of lower case, upper case letters and digits from 0 to 9

Ie. si incontra una 'stringa'

Sembra che tu abbia già identificato il problema. In questo, non c'è modo di determinare una divisione sullo stato 1 perché entrambi i percorsi condividono il sottoinsieme comune [A-Z] [a-z] *. Per creare una NFA valida devi prima identificare i vincoli.

Per iniziare guarderei i casi in cui l'input iniziale è non un 'employee_name'.

Tali casi includono:

• il primo carattere è un carattere alfa in minuscolo
• si incontra un carattere numerico

Inoltre, sia un "nome_dipendente" sia una "stringa" possono essere costituiti dal sottoinsieme identico [A-Z] [a-z] *. Per coprire questa condizione dovrebbe esserci una suddivisione a due vie nella quale si incontra [] o [.]. Dove [] si incontra transiterà quello che è attualmente lo stato 4. Dove [.] Viene incontrato passerai a quello che è attualmente lo stato 10.

Ora che tutti i vincoli sono identificati, è solo questione di ri-mappare il diagramma di stato per rappresentare il flusso. Ci dovrebbe essere un altro stato contenente un ripetitore * per l'elaborazione del resto del valore 'stringa' e altre 3 transizioni. È solo questione di posizionarli correttamente.

Dopo ciò che ha detto @Frank, dovresti eliminare anche due degli stati usando * invece di + per la ripetizione perché il vincolo 1 o più è tecnicamente scorretto. Ad esempio, un nome utente valido potrebbe contenere solo un carattere di [A-Z] e nessun carattere aggiuntivo prima di [_]. Lo stesso schema si applica al "cognome"

da 1 a 9 rimuovi la transizione [A-Z] e aggiungi le transizioni da 2 e 3 a 9 con [A-Z0-9]