Não sou especialista, mas acho que essa suposição está correta.
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.
Parece que você tem uma boa compreensão, mas vou soletrar apenas para ser meticuloso.
A seguir, estão as etapas para converter o NFA atual em um DFA. O primeiro passo é avaliar onde o não-determinismo existe para que o problema possa ser mais detalhado.
A divisão inicial precisa acontecer com base em uma dessas duas condições:
The user name can be either the employee’s name followed by a colon and then the department name
Ou seja. um nome 'employee_name' é encontrado
a string of one or more alphanumeric letters consisting of lower case, upper case letters and digits from 0 to 9
Ou seja. uma 'string' é encontrada
Parece que você já identificou o problema. Nisso, não há como determinar uma divisão no estado 1 porque ambos os caminhos compartilham o subconjunto comum [A-Z] [a-z] *. Para criar um NFA válido, primeiro você precisa identificar as restrições.
Para começar, eu olharia para separar casos em que a entrada inicial não é e 'employee_name'.
Tais casos incluem:
- o primeiro caractere é um caractere alfabético minúsculo
- um caractere numérico é encontrado
Além disso, tanto um 'employee_name' quanto uma 'string' podem ser compostos do subconjunto idêntico [A-Z] [a-z] *. Para cobrir essa condição, deve haver uma divisão bidirecional onde [<>] ou [.] Seja encontrado. Onde [] é encontrado, você faria a transição do estado atual 4. Onde [.] É encontrado, você faria a transição para o que é atualmente o estado 10.
Agora que todas as restrições foram identificadas, é apenas uma questão de mapear novamente o diagrama de estado para representar o fluxo. Deve haver mais um estado contendo um repetidor * para processar o restante do valor 'string' e mais 3 transições. É só uma questão de colocá-los corretamente.
Seguindo o que @Frank disse, você também deve eliminar dois dos estados usando * em vez de + para repetição porque a restrição 1-or-more está tecnicamente incorreta. Por exemplo, um nome de usuário válido pode conter apenas um caractere de [A-Z] e nenhum caractere adicional antes de [_]. O mesmo padrão se aplica ao 'sobrenome'