Construindo um autômato de estado finito

5

Eu tenho uma pergunta do exame que não tenho certeza da resposta. A questão é:

In organisation X valid user names have the following structure. The user name can be either the employee’s name followed by a colon and then the department name or a string of one or more alphanumeric letters consisting of lower case, upper case letters and digits from 0 to 9. All user names end with a period ("."). The employee’s name is expressed as first name followed by an underscore and then the surname. The first name and the surname must begin with an uppercase letter and is followed by an arbitrary number of lower case letters. All department names are an arbitrary number of lower case letters. Express the language for valid user names as a regular expression.

A resposta que tenho é

[A-Z][a-z]+"_"[A-Z][a-z]+":"[a-z]+"." | [A-Za-z0-9]+"."

A próxima pergunta é:

Construct a deterministic finite state automaton for recognising the user names as described in Question 1.

Para o qual eu tenho isto:

Estou com a impressão de que isso está errado, porque [A-Z] é um subgrupo de [A-Za-z0-9] e um DFA não pode ter o mesmo símbolo de um estado. Alguém tem uma idéia de como resolver isso?

Obrigado!

    
por TomSelleck 03.01.2013 / 15:12
fonte

3 respostas

1

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.

    
por 03.01.2013 / 17:57
fonte
1

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'

    
por 03.01.2013 / 18:56
fonte
0

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

    
por 03.01.2013 / 15:28
fonte