Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 46 стр.

UptoLike

ВУЗ: 

ВСГУТУ | Улан-Удэ

Составители: 

Рубрика: 

Преобразователь М начинает работу в состоянии q
0
и, чередуя состояния q
0
и q
4
на
входном символе «−», определяет, четное или нечетное число знаков − предшествует
первому символу а. Когда появляется а, преобразователь М переходит в состояние q
1
,
допуская вход, и выдает а или −а в зависимости от того, четно или нечетно число
появившихся минусов. Для следующих символов а он подсчитывает, четно или нечетно
число предшествующих минусов, с помощью состояний q
2
и q
3
. Единственное различие
между парами q
2
, q
3
и q
0
, q
4
состоит в том, что если символу а предшествует четное число
минусов, то первая из них выдает +а, а не только а.
Таблица переходов выглядит следующим образом:
Y K
К\Х a +
−
a +
−
q
0
a
ε ε
q
1
q
0
q
4
q
1
-
ε ε
- q
2
q
3
q
2
+a
ε ε
q
1
q
2
q
3
q
3
−a ε ε
q
1
q
3
q
2
q
4
−a ε ε
q
1
q
4
q
0
5.7.2. Автомат Мура
Автомат Мура - это «пятерка» вида U = (К
1
, X, Y, f
1
, h), где:
K
1
- множество состояний автомата;
X - входной алфавит;
Y - выходной алфавит;
f
1
- функция переходов (отображение K ⋅ X → K);
h - функция выходов (отображение K ⋅ X → Y).
При представлении автомата Мура графом дуги помечаются символами входного
алфавита, а каждая вершина графа - состоянием и символом выходного алфавита.
При формальном сравнении определений автоматов Мили и Мура может показаться, что
автомат Мура может быть задан как входонезависимый автомат Мили, т.е. такой автомат
Мили, выходная функция которого удовлетворяет следующим условиям: ∀ a ∈ X, ∀ b ∈ X, ∀
z ∈ Z (g(z, a) = g(z, b)). Однако это не соответствует способу функционирования автоматов
Мура в соответствии с введенным определением.
В автомате Мура реализована иная временная связь между переходами из одного
состояния в другое и выходом, по сравнению с автоматом Мили, у которого выход,
соответствующий некоторому входу и определенному состоянию, порождается во время
перехода автомата в следующее состояние. У автомата Мура сначала порождается выход, а
потом - переход в следующее состояние, причем выход определяется только состоянием
автомата. 
        Преобразователь М начинает работу в состоянии q0 и, чередуя состояния q0 и q4 на
  входном символе «−», определяет, четное или нечетное число знаков − предшествует
  первому символу а. Когда появляется а, преобразователь М переходит в состояние q1,
  допуская вход, и выдает а или −а в зависимости от того, четно или нечетно число
  появившихся минусов. Для следующих символов а он подсчитывает, четно или нечетно
  число предшествующих минусов, с помощью состояний q2 и q3. Единственное различие
  между парами q2, q3 и q0, q4 состоит в том, что если символу а предшествует четное число
  минусов, то первая из них выдает +а, а не только а.
         Таблица переходов выглядит следующим образом:
                                       Y                K
                            К\Х   a    +    −     a     +     −
                             q0    a   ε    ε     q1    q0    q4
                             q1    -   ε    ε     -     q2    q3
                             q2   +a   ε    ε     q1    q2    q3
                             q3   −a   ε    ε     q1    q3    q2
                             q4   −a   ε    ε     q1    q4    q0

      5.7.2. Автомат Мура
   Автомат Мура - это «пятерка» вида U = (К1, X, Y, f1, h), где:

   K1 - множество состояний автомата;
   X - входной алфавит;
   Y - выходной алфавит;
   f1 - функция переходов (отображение K ⋅ X → K);
   h - функция выходов (отображение K ⋅ X → Y).

    При представлении автомата Мура графом дуги помечаются символами входного
алфавита, а каждая вершина графа - состоянием и символом выходного алфавита.
    При формальном сравнении определений автоматов Мили и Мура может показаться, что
автомат Мура может быть задан как входонезависимый автомат Мили, т.е. такой автомат
Мили, выходная функция которого удовлетворяет следующим условиям: ∀ a ∈ X, ∀ b ∈ X, ∀
z ∈ Z (g(z, a) = g(z, b)). Однако это не соответствует способу функционирования автоматов
Мура в соответствии с введенным определением.
    В автомате Мура реализована иная временная связь между переходами из одного
состояния в другое и выходом, по сравнению с автоматом Мили, у которого выход,
соответствующий некоторому входу и определенному состоянию, порождается во время
перехода автомата в следующее состояние. У автомата Мура сначала порождается выход, а
потом - переход в следующее состояние, причем выход определяется только состоянием
автомата.

Страницы