Конечный датчик, который вычисляет отношение - PullRequest
Новая
       26

Конечный датчик, который вычисляет отношение

2 голосов
/ 04 марта 2012

С http://www.cse.ohio -state.edu / ~ gurari / теория-bk / теория-bk-twoli1.html # 30007-23021r2.2.4 :

Пусть Mзнак равнобыть детерминированным датчиком конечных состояний, диаграмма перехода которого приведена в Рисунок 2.E.2 .

Figure 2.E.2

Для каждого из следующих соотношений найти конечноедатчик состояния, который вычисляет отношение.

a.{(х, у) |х находится в L (M), а у находится в Δ *}.б.{(х, у) |х в L (M), у в Δ *, а (х, у) не в R (М)}.

Да, это HW, но я боролся сэти вопросы и могли бы хотя бы использовать указатели.Если вы хотите создать свой собственный c.и / или d.примеры только для того, чтобы показать мне, как это сделать, а не привести меня к ответам для.и б.тогда, очевидно, я в порядке с этим.

Заранее спасибо!

1 Ответ

2 голосов
/ 04 марта 2012

Поскольку вы не указываете, какого прогресса вы достигли до сих пор, я предполагаю, что вы вообще не достигли прогресса, и предоставлю общее руководство о том, как вы можете решить эту проблему.

  • Прежде всего, изучите диаграмму переходов.Вы понимаете, что означают все обозначения?Обратите внимание, что датчик описан как детерминированный .Вы понимаете, что это значит?Убедитесь сами, что преобразователь, изображенный на диаграмме переходов, фактически является детерминированным.Проследить через это;попытайтесь понять, какие входные сигналы принимаются датчиком и какие выходы он дает.
  • Затем выясните, какие значения L (M), Δ и R (M) предназначены для этого датчика, посколькувопросы относятся к ним.Знаете ли вы, что означают эти обозначения?
  • Знаете ли вы, что означает для преобразователя вычисление определенного отношения?Вы понимаете {(x, y) |...} нотация для описания отношения?
  • Можете ли вы изменить диаграмму переходов, чтобы исключить переход ε / 0 и объединить его в смежные переходы (которые затем могут выводить несколько символов за один переход)?(Это может помочь, ИМХО, с созданием других преобразователей, которые принимают тот же язык ввода. В данном случае это больше относится к части b , чем к части a .)
  • Опишите для себя преобразователи, которые вам нужно создать, способом, который не зависит от исходного преобразователя.Будут ли эти преобразователи детерминированными?
  • Создать диаграммы перехода для этих преобразователей.
...