Construindo um autômato de estado finito

Como apontado nos comentários arbitrary pode incluir 0 , você deve ter * em vez de + em sua expressão regular nos locais correspondentes.

A partir de sua expressão regular original, você derivou corretamente um autômato de estado finito não determinístico (NFA). Para adaptá-lo ao * mencionado acima, você só precisa eliminar os estados 2 e 5 para ter um NFA correspondente novamente.

A parte interessante da questão do exame é derivar uma máquina de estados finita determinística do seu NFA. Isso é mecanicamente possível por meio de um algoritmo chamado de construção do conjunto de potência . Esse link deve fornecer informações suficientes (e você deve ter aprendido em suas lições, de acordo com a questão do exame!) Para aprender como ir do NFA ao DFA.

O DFA resultante geralmente é muito grande devido ao conjunto de estados, que é a razão pela qual normalmente se realiza uma minimização do DFA depois. Embora, para ser honesto, eu pularia isso, já que a pergunta só pede um DFA, não um mínimo DFA.

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'

de 1 a 9, remova a transição [A-Z] e adicione as transições 2 e 3 a 9 com [A-Z0-9]