Формальные языки, грамматики и основы построения трансляторов. Кревский И.Г - 36 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

36
Так как А есть последнее состояние, строка принимается конечным
автоматом, однако при чтении строки
0 0 1 1 1
автомат проходит через состояния
А, А, А, В, А, В
поскольку В не является последним состоянием, эта строка не
принимается, т.е. она не принадлежит языку, принимаемому этим автоматом.
В связи с тем, что нули не
влияют на состояние автомата, а каждая единица
изменяет его состояние с А на В и с В на А, и начальное состояние является
тем же, что и последнее состояние, язык, принимаемый автоматом, состоит
из тех строк, которые содержат четное число единиц.
Переходы можно представить с помощью таблицы (таблица 6.1) и
схематически (рис
.6.1).
Таблица 6.1
Состояния
А В
0
А В
Вход
1
В А
A
B
0
1
1
0
Рис.6.1. Переходы детерминированного конечного автомата.
Такой автомат называют детерминированным
, потому что в каждом
элементе таблицы переходов содержится одно состояние. В
недетерминированном конечном автомате это положение не выдерживается.
Рассмотрим конечный автомат, определяемый следующим образом:
M
1
= ( K
1
,
Σ
1
,
δ
1
, S
1
, f
1
), 
                                                                                         36
       Так как А есть последнее состояние, строка принимается конечным
автоматом, однако при чтении строки
       00111
       автомат проходит через состояния
       А, А, А, В, А, В
       поскольку В не является последним состоянием, эта строка не
принимается, т.е. она не принадлежит языку, принимаемому этим автоматом.
В связи с тем, что нули не влияют на состояние автомата, а каждая единица
изменяет его состояние с А на В и с В на А, и начальное состояние является
тем же, что и последнее состояние, язык, принимаемый автоматом, состоит
из тех строк, которые содержат четное число единиц.
       Переходы можно представить с помощью таблицы (таблица 6.1) и
схематически (рис.6.1).
                                                      Таблица 6.1
                                          Состояния
                                                       А     В
                                   Вход       0        А     В
                                              1        В     А


                                   0              1              0
                                   A                           B
                                                  1
          Рис.6.1. Переходы детерминированного конечного автомата.


       Такой автомат называют детерминированным, потому что в каждом
элементе       таблицы            переходов       содержится         одно   состояние.   В
недетерминированном конечном автомате это положение не выдерживается.
       Рассмотрим конечный автомат, определяемый следующим образом:
M1 = ( K1, Σ 1, δ 1, S1 , f1 ),

Страницы