Пассивное обучение в конечных автоматах

Я читаю следующий абзац в книге «Основы машинного обучения» https://cs.nyu.edu/~mohri/mlbook/ на странице 362 (книги).

введите здесь описание изображения

Сейчас я новичок в концепции DFA, но у меня есть некоторый опыт. У меня есть вопросы по абзацу.

  1. Зачем им нужен детерминированный автомат, который принимает положительно помеченную строку «a» или «b»? Конечно, вы хотели бы отклонить $"b"$, так как он помечен отрицательно?

  2. Является ли «a» строкой символов, т.е. a = 01010101, или это одна буква?

  3. Каков минимальный автомат с двумя состояниями, который принимает «a» или «b», может ли кто-нибудь его описать? Также я не уверен, чем он отличается от машины с одним конечным состоянием, которую они описывают далее для языка a* ? Может ли кто-нибудь явно описать оба? Я не вижу, в чем разница между двумя случаями, и, может быть, поэтому я не понимаю, почему у одного есть два состояния, а у другого - одно состояние.

Я был бы очень признателен за любую помощь, поскольку я действительно пытаюсь понять концепции, о которых они говорят.


state-machine deterministic computation-theory finite-automata
person Pavan Sangha    schedule 19.05.2020    source источник

Ответы (1)


arrow_upward
0
arrow_downward

  1. им нужен DFA с как можно меньшим количеством состояний, который принимает строку «a» и отклоняет строку «b»
  2. «a» означает символ a, а не сокращение, представляющее битовую строку, которую вы дали. В теории формального языка допускается использование букв в качестве символов.
  3. Здесь они пытаются провести различие между DFA с наименьшим количеством состояний, который принимает «a» и отвергает «b», и минимальным DFA, принимающим язык {'a'}. Увидеть ниже.

Наименьший DFA, который принимает «a» и отклоняет «b», на самом деле имеет два состояния, если вы используете стандартные соглашения о том, что должны быть представлены мертвые состояния и должны быть показаны все переходы:

       +--a--+
       |     |
----->q0<----+
       |
       b
       |
       V
      q1<----+
       |     |
       +-a,b-+

В приведенном выше DFA q0 является принимающим. Ни один DFA меньшего размера не принимает «a» и не отвергает «b». Вы знаете это, поскольку DFA должен иметь принимающее состояние, чтобы принять что-либо, и непринятое состояние, чтобы отвергнуть что-либо, а поскольку состояние не может быть обоими одновременно, нам нужно два. Теперь различие, к которому приводит цитируемый отрывок, заключается в том, что DFA, который принимает язык {'a'}, больше (поскольку он исключает все, кроме 'a', а не только 'b'):

----->q0--a-->q1
      |       |
      b      a,b
      |       |
      |       V
      +------>q2<---+
              |     |
              +-a,b-+

Здесь q1 принимает. Обратите внимание, что нам нужно дополнительное состояние, чтобы избежать приема более длинных строк 'a'.

person Patrick87    schedule 19.05.2020
comment
Но почему сказано, что DFS, принимающая язык $'a'$, имеет только одно состояние? Тот, который вы нарисовали, имеет три состояния - person Pavan Sangha; 19.05.2020
comment
Существует DFA, который принимает 'a' (среди прочего), который имеет одно состояние: DFA с одним состоянием, который принимает каждую строку. К сожалению, этот DFA также принимает «b», поэтому мы не можем его использовать. Принять «а» и отклонить «b» можно с помощью двух состояний: принять любую строку «а», оставаясь в начальном состоянии, и перейти в мертвое состояние, если вы когда-нибудь увидите «b». Чтобы точно принять язык «а», требуется три состояния: начальное (все еще нужно одно «а»), принимающее (увидел наше одно «а») и мертвое (увидел больше/другое, чем просто «а»). Если в книге сказано иначе, в книге используются соглашения, с которыми я не знаком, или это неправильно. - person Patrick87; 19.05.2020
comment
спасибо, книга довольно неясна в своем объяснении - person Pavan Sangha; 20.05.2020