Я всегда обнаруживал, что самый простой способ думать об этом (так как набор состояний конечен) состоит в том, чтобы каждое из этих подмножеств представляло собой кодировку числа base-2 в диапазоне от 0 (все биты ноль) до 2 | Q | -1 (все биты один), где в числе столько битов, сколько членов в наборе состояний, Q. Затем вы можете просто взять одно из этих чисел и отобразить егов подмножество, используя, установлен ли определенный бит в числе.Легко!
Вот рабочий пример, где Q = { a , b , c }.В этом случае | Q |равно 3 (есть три элемента) и поэтому 2 3 равно 8. Это означает, что мы получим это, если скажем, что ведущий бит предназначен для элемента a , следующий бит для b и завершающий бит для c :
- 0 = 000 = {}
- 1 = 001= { c }
- 2 = 010 = { b }
- 3 = 011 = { b, c }
- 4 = 100 = { a }
- 5 = 101 = { a, c }
- 6 = 110 ={ a, b }
- 7 = 111 = { a, b, c }
Видите?Эти первоначальные три состояния были преобразованы в 8, и у нас есть их естественная нумерация, которую мы могли бы использовать для создания меток этих состояний, если мы выбрали.
Теперь, чтобы интерпретировать это в недетерминированный контекст.По сути, недетерминизм означает, что мы не уверены в том, в каком состоянии мы находимся. Мы представляем это с помощью псевдосостояния, которое представляет собой набор «реальных» состояний, в которых мы могли бы находиться;если мы имеем полный недетерминизм, то мы находимся в псевдосостоянии, где возможны все действительные состояния (т. е. { a, b, c }), тогда как псевдосостояние, в котором нет действительных состоянийвозможным (т. е. {}) является обратное (и действительно должно быть невозможно достичь в переходной системе).В реальной системе вы обычно не имеете дело ни с одной из этих крайностей.
Логика того, как вы преобразуете детерминированную систему перехода в недетерминированную, довольно сложна, чем я хочу здесь остановиться.,(Я должен был прочитать серьезную докторскую диссертацию, чтобы выучить ее, так что это определенно больше, чем стоит SO-ответ!)