Минимизация полностью определённых автоматов

• 1 слайд

  Минимизация полностью определённых автоматов
  
  

• 2 слайд

  Алгоритм минимизации числа внутренних состояний полностью определённого автомата
  
  Находятся последовательные разбиения , ,… множества X до тех пор, пока на каком-то (k+1) шаге не окажется, что это разбиение ничем не отличается от предыдущего. Доказано, что в этом случае ( = ) и есть необходимое нам разбиение, и дальнейшее сокращение числа внутренних состояний автомата невозможно.
  
  

• 3 слайд

  Алгоритм минимизации числа внутренних состояний полностью определённого автомата
  
  В каждом классе эквивалентности разбиения выбирается по одному элементу, который образует множество X’.
  
  
  
  
  

• 4 слайд

  Алгоритм минимизации числа внутренних состояний полностью определённого автомата
  3. Функции переходов и функция выходов для автомата определяются на множестве оставшихся внутренних состояний и множестве входных сигналов. Для этого в таблице переходов вычеркиваются столбцы, соответствующие состояниям, не вошедшим в множество , а в оставшихся столбцах таблицы переходов все состояния заменяются на эквивалентные из множества . В таблице выходов столбцы вычёркиваются.
  4. В качестве начального состояния выбирается одно из состояний, эквивалентных X0. На практике лучше взять само X0.
  

• 5 слайд

  Минимизация автомата Мили
  Таблица переходов
  Таблица выходов
  ={X1,X2,X5,X7,X8} B1,
  {X3,X4,X6,X9,X10,X11,X12 } B2
   
  
  

• 6 слайд

  Минимизация автомата Мили
  ={X1,X2} C1,
  {X5,X7,X8} C2,
  {X3,X4,X6,X9,X11} C3,
  {X10,X12} C4,
  
  

• 7 слайд

  Минимизация автомата Мили
  = {X1,X2} D1,
  {X5,X7} D2
  {X8} D3
  {X3,X4,X6,X9,X11} D4
  {X10,X12} D5
  
  

• 8 слайд

  Минимизация автомата Мили
  Таблица переходов
  {X1,X2} D1,
  {X5,X7} D2
  {X8} D3
  {X3,X4,X6,X9,X11} D4
  {X10,X12} D5
  
  

• 9 слайд

  Минимизация автомата Мили
  Таблица выходов
  

• 10 слайд

  Минимизация автомата Мура
  = {X1, X2, X8} A1
  {X6, X9, X10, X11, X12} A2
  {X3, X4, X5, X7} A3