конечный автомат помогите, не могу понять эту концепцию

Предположим, что конечный автомат достигает состояния s после обработки слова w. Как мы можем сказать, принадлежит ли w языку (или нет) автомата, если s является конечным или неконечным, а автомат является ДКА или НКА (4 случая).

Это беспокоило меня. Любая помощь будет высоко оценена!


automation dfa nfa
person jason    schedule 28.04.2015    source источник
comment
Не могли бы вы добавить немного больше описания проблемы, с которой вы столкнулись?   -  person abarisone    schedule 28.04.2015
comment
Это был вопрос, на котором я застрял :( Это один из вопросов, который у нас был в классе, но я не мог его понять. Он спрашивал, есть ли какие-либо способы, которыми мы можем сказать, что слово принадлежит языку после того, как оно достигает состояния S .. И если мы можем сказать, является ли состояние S конечным состоянием или нет, и является ли эта автоматизация DFA или NFA..   -  person jason    schedule 28.04.2015
comment
@jason, твой вопрос не ясен. Я бы посоветовал еще раз прочитать ваш учебник. В любом случае, NFA и DFA - это две формы FA (конечные автоматы), прочитайте этот пост. А состояния в FA могут быть как окончательными, так и нефинальными. Если после обработки строка w последнее состояние является окончательным, то строка w считается принятой. Я бы посоветовал вам прочитать задавать вопросы в StackOverflow   -  person Grijesh Chauhan    schedule 28.04.2015

Ответы (1)


arrow_upward
0
arrow_downward

FSA для языка L после чтения w может остановиться в наборе состояний Qw . w тогда является членом L тогда и только тогда, когда существует хотя бы одно конечное (принимающее) состояние qf в Qw. Другими словами: если FSA, читая w, может остановиться в конечном состоянии, то w является членом L< /эм>.

DFA, читающий одни и те же входные данные, всегда будет приходить в одно и то же состояние; отсюда и название. Итак, здесь Qw всегда состоит из одного состояния, и ответ прост: если состояние является конечным состоянием, то w является член языка; в противном случае это не так.

С NFA сложнее, потому что если вы запустите его на w, он может остановиться в любом состоянии в Qw. Если это принимающее состояние, по определению вы знаете, что w является членом L. Ура, повезло! Но что, если после прочтения w мы достигнем не конечного состояния? Можем ли мы сказать, подобно DFA, что w не является членом L?

К сожалению нет*. Рассмотрим эти два NFA:

  • NFA1, чтение w, может останавливаться на qnf1 и qnf2, оба неконечные состояния;
  • NFA2, чтение w, может останавливаться на qnf1 и qnf2, но и в qf, конечном состоянии.

Допустим, мы скормили w нашей машине, и она остановилась на qnf1. Что мы можем сказать о w, не зная, какой NFA мы тестируем? Явно ничего: w является членом L2, потому что, если бы мы продолжали работать с NFA2< /em> на w, рано или поздно мы можем оказаться в qf ; с другой стороны, w не является членом L1, потому что независимо от того, сколько раз мы запускаем w через NFA1 мы можем оказаться только в непринятых состояниях.

Итак, подводя итог:

  • DFA, конечное состояние: да
  • NFA, конечное состояние: да
  • DFA, не конечное состояние: нет
  • NFA, не конечное состояние: мы не знаем

* Я предположил, что FSA для нас — это черные ящики, и все, что мы можем наблюдать, — это слово w и состояние, в котором мы останавливаемся, < эм>к. Если бы мы знали структуру FSA, случай NFA был бы намного проще, потому что мы могли бы просто проверить Qw.

person David Nemeskey    schedule 03.05.2015