DFA для представления пароля

Я хочу создать DFA для пароля со следующими ограничениями:

  • он должен быть длиной 8 символов
  • он должен содержать не менее двух символов нижнего регистра: [a-z]
  • он должен содержать хотя бы один символ верхнего регистра: [A-Z]
  • он должен содержать как минимум два десятичных числа: [0-9]
  • он должен содержать хотя бы один из следующих специальных символов: [!.@*_]
  • он должен начинаться со специального символа

Как создать этот DFA?


dfa computation-theory
person Mohamed Horani    schedule 05.03.2016    source источник
comment
Это будет очень большой DFA...   -  person Oliver Charlesworth    schedule 06.03.2016
comment
В том то и дело, есть ли способ его минимизировать?   -  person Mohamed Horani    schedule 06.03.2016

Ответы (1)


arrow_upward
3
arrow_downward

Любой DFA для этого языка должен помнить как минимум

  • сколько строчных букв было прочитано (0, 1 или 2 и более),
  • сколько заглавных букв было прочитано (0, 1 или более) и
  • сколько десятичных цифр было прочитано (0, 1 или 2 или более).

Это дает вам как минимум 18 состояний, и это даже не учитывает ограничения по длине. Я не думаю, что вы найдете простой DFA для этого языка. Он просто будет большим.

Теперь вы можете построить довольно простой, но большой DFA, создав один DFA для каждого ограничения (ни одно из них не так уж плохо), а затем выполнив многофакторное конструирование продукта, чтобы создать DFA для всего языка. Я думаю, что это наиболее теоретически элегантный способ сделать это, и на самом деле это довольно легко представить в программном обеспечении. Если бы мне пришлось построить DFA, я бы сделал это так.

person templatetypedef    schedule 06.03.2016