1. Смешанное состояние без e-переходов.
1.1. Императивный автомат (рис.2.3.1).
Mi0=Mi3=Mi2=Mi1 | A | ||
1
| x:(v, x,vx) |
| x:(v, x,vx) |
Рис.2.3.1
Для каждого состояния v типа 1 добавляется дополнительное состояние (v,e). Посылающий (v,y,v`y) или пустой (v,v`y) переход из v заменяется на e-переход, ведущую в дополнительное состояние (e,v,(v,e)) и, соответственно, посылающий ((v,e),y,vy) или пустой ((v,e),vy) переход из этого дополнительного состояния.
1.2. Факультативный автомат (рис.2.3.2).
M`f0=M`f3=M`f2=M`f1 | A | ||
1
| x:(v, x,vx) |
| x:(v, x,(v, x))+((v, x),vx) |
Рис.2.3.2
Аналогично случаю 1.1, для каждого состояния v типа 1 добавляется дополнительное состояние (v,e); посылающий (v,y,v`y) или пустой (v,v`y) переход из v заменяется на e-переход в дополнительное состояние (e,v,(v,e)) и, соответственно, посылающий ((v,e),y,vy) или пустой ((v,e),vy) переход из этого дополнительного состояния. Затем в моделирующий автомат добавляются дополнительные состояния вида (v,x) для состояний vÎV и непустых стимулов xÎX. Для каждого основного смешанного состояния vÎV рассматриваемого типа и допустимого в нем непустого стимула x добавляется принимающий переход (v,x,(v,x)). В каждом дополнительном состоянии (v,x) определяются посылающие ((v,x),y,(v`,x)) и пустые ((v,x),(v`,x)) переходы тогда и только тогда, когда в моделируемом автомате есть переходы, соответственно, (v,y,v`) и (v,v`). В каждом дополнительном состоянии (v,x) определяется пустой переход ((v,x),v`) тогда и только тогда, когда в моделируемом автомате есть переход (v,x,v`).
2. Смешанное состояние, в котором все принимающие переходы - e-переходы.
2.1. Равный приоритет e-переходов и посылающих и пустых переходов (рис.2.3.3).
Mi3=M`f3 | A | ||
2
| e:(v, e,ve) |
| e:(v, e,ve) |
Рис.2.3.3
Аналогично случаю 1.1, для каждого состояния v типа 2 добавляется дополнительное состояние (v,e); посылающий (v,y,v`y) или пустой (v,v`y) переход из v заменяется на e-переход в дополнительное состояние (e,v,(v,e)) и, соответственно, посылающий ((v,e),y,vy) или пустой ((v,e),vy) переход из этого дополнительного состояния.
2.2. Приоритет e-переходов (рис.2.3.4).
Mi2=M`f2 | A | ||
2
| e:(v, e,ve) |
| e:(v, e,ve) |
Рис.2.3.4
Приоритет e-переходов приводит к тому, что в состоянии типа 2 вообще никогда не будут выполняться посылающие и пустые переходы, поэтому их можно удалить.
2.3. Приоритет посылающих и пустых переходов (рис.2.3.5).
Mi1=M`f1 | A | ||
2
| e:(v, y,vy) |
| e:(v, e,(v, e))+((v, e),y, vy) |
Рис.2.3.5
Приоритет посылающих и пустых переходов приводит к тому, что в состоянии типа 2 вообще никогда не будут выполняться e-переходы. Однако, если такие переходы просто удалить, то состояние перестанет быть рецептивным. Поэтому, как и в случае 1.1, для каждого состояния v типа 2 добавляется дополнительное состояние (v,e); посылающий (v,y,v`y) или пустой (v,v`y) переход из v заменяется на e-переход в дополнительное состояние (e,v,(v,e)) и, соответственно, посылающий ((v,e),y,vy) или пустой ((v,e),vy) переход из этого дополнительного состояния.
3. Смешанное состояние общего вида.
3.1. Императивный автомат.
3.1.1. Равный приоритет e-переходов и посылающих и пустых переходов (рис.2.3.6).
Mi3 | A | ||
3
| x:(v, x,vx) |
| x:(v, x,vx) |
Рис.2.3.6
Аналогично случаю 2.1, для каждого состояния v типа 3 добавляется дополнительное состояние (v,e); посылающий (v,y,v`y) или пустой (v,v`y) переход из v заменяется на e-переход в дополнительное состояние (e,v,(v,e)) и, соответственно, посылающий ((v,e),y,vy) или пустой ((v,e),vy) переход из этого дополнительного состояния.
3.1.2. Приоритет e-переходов (рис.2.3.7).
Mi2 | A | ||
3
| x:(v, x,vx) |
| x:(v, x,vx) |
Рис.2.3.7
Аналогично случаю 2.2, приоритет e-переходов приводит к тому, что в состоянии типа 3 вообще никогда не будут выполняться посылающие и пустые переходы, поэтому их можно удалить.
3.1.3. Приоритет посылающих и пустых переходов (рис.2.3.8).
Mi1 | A | ||
3
| x:(v, x,vx) |
| x:(v, x,vx) |
Рис.2.3.8
Приоритет посылающих и пустых переходов приводит к тому, что в состоянии типа 3 вообще никогда не будут выполняться e-переходы. Удаляя e-переходы, получаем случай 1.1 и применяем соответствующее преобразование.
3.2. Факультативный автомат.
3.2.1. Равный приоритет e-переходов и посылающих и пустых переходов (рис.2.3.9).
M`f3 | A | ||
3
| x:(v, x,vx) |
| x:(v, x,(v, x))+((v, x),vx) |
Рис.2.3.9
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
