Нужна помощь в построении детерминированных конечных автоматов?

Question

Каковы правила построения детерминированных конечных автоматов в виде диаграммы? Мой профессор объяснил примерами, но я не совсем уверен, какие правила должны соблюдаться всеми диаграммами. Любая помощь приветствуется, спасибо!

Answer 1

Off верхней части моей головы, в DFA, вот основные правила, (термины, специфичные для ДКА в двойных кавычках): -

• каждое «государство» должно иметь «переход «для каждого« ввода », определенного в DFA
  , поэтому это означает, что для каждого входа, который рассматривается в dfa, для состояния, должен быть определен переход, чтобы можно было узнать, куда идти от этого состояния для каждого входа.
  

• каждое «состояние» может иметь только один «переход» для каждого «входа»
  хорошо это правило говорит само за себя, так что если вы уже определили переход на вход для конкретного состояния, дон» t создать другой переход для одного и того же входа из одного и того же состояния.
  

Да, это те, кого я помню. Надеюсь, поможет. Далее эти точки можно использовать для дифференциации dfa от nfa. Другие простые правила для рисования будут: -

• сделать начальное состояние, обозначено стрелкой, указывающей к государству
  

• имеют по крайней мере один конечное состояние, показано с концентрическими кругами втянуть государство граница
  

• рисовать переходы в виде стрелок
  

• метки все переходы с т соответствующие соответствующим входным символам