Теория автоматов. - 7 стр.

UptoLike

ВУЗ: 

ПНИПУ | Пермь

Рубрика: 

Таблица 8 Таблица 9
1 – эквивелентные классы определяются из табл. 8 , 2 – эквивалентные из
табл. 9 , а 3 – эквивалентные и просто эквивалентные из табл. 10 .
Таблица 10 Таблица 11 Таблица 12
В качестве имен состояний минимального автомата возьмем име-
на классов. Минимальный автомат представлен табл. 11 и 12.
РАСПОЗНАЮЩИЕ АВТОМАТЫ
Распознающий автомат – это автомат Мура, в котором фиксируется на-
чальное состояние и подмножество состояний F
⊆
Q, называемое множеством
заключительных состояний. Говорят, что автомат допускает (принимает, распо-
знает, представляет) данное слово, если реакцией на это слово может быть пе-
реход автомата в одно из заключительных состояний.
Примеры. 1. Автомат (рис. 4) с начальным состоянием 1 и заключитель-
ным F
1
и F
2
допускает слова, в которых имеются только парные вхождения букв
a и b, например, a a, a a a a a a, b b a a и т.д.
Рис. 4
2.Для распознавания часто используются частичные автоматы (рис.5),
допускающие тоже множество слов, что и автомат, показанный на рис.4.
1 2 3 4 5 6
x
1
y
1
y
1
y
1
y
1
y
1
y
2
x
2
y
2
y
2
y
2
y
2
y
2
y
2
1 2 3 4 5 6
x
1
1
α
4
α
6
β
2
α
6
β
4
α
x
2
2
α
1
α
3
α
2
α
5
α
5
α
α β γ
x
1
α γ α
x
2
α β β
α β γ
x
1
y
1
y
1
y
2
x
2
y
2
y
2
y
2
1 2 4 3 5 6
x
1
1
α
4
α
2
α
6
γ
6
γ
4
α
x
2
2
α
1
α
2
α
3
β
5
β
5
β
α β α β α β γ 
                               Таблица 8                                                               Таблица 9
                       1       2           3           4       5   6                       1           2       3       4        5       6
                                                                                  x1       1           4       6       2        6       4
              x1       y1 y1 y1 y1 y1 y2                                                       α           α       β       α        β    α
                                                                                  x2       2           1       3       2        5       5
              x2       y2 y2 y2 y2 y2 y2                                                       α           α       α       α        α     α
                                       α                           β                               α           β        α        β       γ

       1 – эквивелентные классы определяются из табл. 8 , 2 – эквивалентные из
табл. 9 , а 3 – эквивалентные и просто эквивалентные из табл. 10 .

                   Таблица 10                                               Таблица 11                                         Таблица 12
          1        2       4       3           5           6                  α        β           γ                            α        β    γ
          1        4       2       6           6           4
    x1        α        α       α       γ           γ        α          x1     α        γ           α                   x1       y1       y1   y2
          2        1       2       3           5           5
    x2        α        α       α       β           β         β         x2     α        β           β                   x2       y2       y2   y2

                В качестве имен состояний минимального автомата возьмем име-
         на классов. Минимальный автомат представлен табл. 11 и 12.



                                                   РАСПОЗНАЮЩИЕ АВТОМАТЫ

        Распознающий автомат – это автомат Мура, в котором фиксируется на-
чальное состояние и подмножество состояний F⊆Q, называемое множеством
заключительных состояний. Говорят, что автомат допускает (принимает, распо-
знает, представляет) данное слово, если реакцией на это слово может быть пе-
реход автомата в одно из заключительных состояний.
        Примеры. 1. Автомат (рис. 4) с начальным состоянием 1 и заключитель-
ным F1 и F2 допускает слова, в которых имеются только парные вхождения букв
a и b, например, a a, a a a a a a, b b a a и т.д.
                                                         Рис. 4




      2.Для распознавания часто используются частичные автоматы (рис.5),
допускающие тоже множество слов, что и автомат, показанный на рис.4.

Страницы