Главная > Введение в теорию конечных автоматов
НАПИШУ ВСЁ ЧТО ЗАДАЛИ
СЕКРЕТНЫЙ БОТ В ТЕЛЕГЕ
<< Предыдущий параграф Следующий параграф >>
Пред.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
След.
Макеты страниц

Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше

Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике

ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO

7.2. Совместимость состояний

При определении основной модели с конечным числом состояний (см. § 1.6) молчаливо предполагалось, что характеристические функции конечного автомата определены для каждой пары При изучении автоматов с ограничениями на входе удобно видоизменить эту модель и допустить наличие пар для которых обе функции остаются неопределенными. В частности, мы можем предполагать, что у автомата не определены для пары где — входной символ, а — состояние автомата М, если ни при каких условиях не может быть приложен к при этом говорят, что автомат М имеет ограничение на входе в состоянии таблице переходов автомата М такое ограничение отмечается тем, что клетки в обеих подтаблицах расположенные на пересечении строки I и столбца остаются пустыми (или заполняются прочерками). Входная последовательность называется допустимой в состоянии если при приложении к она не нарушает ограничения на входе ни в каком состоянии автомата М. В качестве примера на рис. 7.1 и в таблице 7.1 представлен автомат (с ограничениями на входе.

Состояния автомата М с ограничениями на входе называются совместимыми, если для при подаче на вход любой допустимой для и входной последовательности на выходе появляется одна и та же

последовательность. Состояния несовместимы, если существует, по крайней мере, одна входная последовательность, допустимая как для так и для , при подаче которой на автомат выдает различные выходные последовательности.

Рис. 7.1. Автомат .

Видно, что совместимость обладает свойствами рефлексивности и симметричности, но не обладает свойством транзитивности, так как последовательности, допустимые для не обязательно допустимы для

Таблица 7.1. Автомат

Совместимость поэтому нельзя понимать как обычное отношение эквивалентности, а следует относить только к парам состояний.

Следует заметить, что определение совместимых пар состояний совпадает с определением эквивалентных пар состояний, если на входные последовательности рассматриваемого автомата не накладываются никакие ограничения. Таким образом, определение совместимости пар состояний может быть получено из определения эквивалентности пар состояний, если в последнем (см. определение 3.1) выражение «любой входной последовательности» заменить выражением «любой входной последовательности, допустимой для обоих состояний» (это изменение не отразится на правильности определения 3.1, так как в автомате без ограничений на входе множество допустимых последовательностей составляет множество всех последовательностей). Поэтому определение пары совместимых состояний производится так же, как определение пары эквивалентных состояний, с той лишь разницей, что все последовательности, недопустимые для обоих состояний пары, не учитываются.

В § 3.7 был описан метод, названный методом таблицы пар, для определения всех эквивалентных пар состояний в данном автомате. В соответствии с приведенными замечаниями этот метод может быть использован для определения всех совместимых пар состояний при условии, что первый вариант таблицы пар видоизменяется следующим образом: (1) элементы в столбце пар представляют собой пары состояний, при которых выдается один и тот же выходной символ при подаче любого входного символа, допустимого для обоих состояний пары; (2) если входной символ недопустим для обоих состояний и то клетка, расположенная на пересечение строки и столбца в таблице пар остается

Таблица 7.2. Таблица пар для автомата

пустой (или заполняется прочерком). Тогда построение последующих вариантов таблиц пар состояний может быть выполнено таким же образом, как это описано в § 3.7. Не выделенные жирным шрифтом элементы столбца пар в конечном варианте таблицы пар представляют все совместимые пары состояний для данного автомата.

Например, таблица 7.2 представляет конечный вариант таблицы пар для автомата изображенного на рис. 7.1. Из таблицы следует, что совместимыми парами в автомате являются:

1
Оглавление
email@scask.ru