В качестве первого примера рассмотрим ситуацию, когда в двери име
 Скачать 14.81 Kb.
|
|
В качестве первого примера рассмотрим ситуацию, когда в двери име- ется два замка, которые мы обозначим A и B. При каждом повороте ключа в любом из этих замков мы переводим соответствующий замок из положения ѕзакрытої в положение ѕоткрытої и наоборот. Состояния этой системы будут определяться открытостью и закрытостью замков A и B. Поэтому мы считаем, что наша система будет иметь 4 состояния: 00: оба замка закрыты, 01: первый замок закрыт, а второй открыт, 10: первый замок открыт, а второй закрыт, 11: оба замка открыты. Воздействовать на нашу систему мы будем поворачиванием ключа в одном из замков A или B (будем обозначать эти воздействия соответ- ственно символми A или B). Очевидно, что все возможные переходы из одного состояния в другое описываются следующей таблицей: 13 14 Глава 2. Автоматные языки 00 01 10 11 A 10 11 00 01 B 01 00 11 10 . Здесь в верхней строке выписаны состояния системы, сбоку перечислены все возможные воздействия, а в соответствующей строке таблицы указа- но состояние, в которое система перейдјт в результате этого воздействия. Разумеется, поворачивая ключи в замках, мы преследуем определјнную цель, например, мы хотим открыть эту дверь. Поэтому состояние 11 иг- рает для нас особую роль (дверь открыта, цель достигнута!), и тогда мы назовјм это состояние выделенным. Стоит сразу заметить, что выделен- ные состояния могут оказаться и другими в случае, если мы преследуем другую цель, например, если наша задача состоит в том, чтобы дверь оставалась закрытой, то выделенных состояний будет уже не одно а три: 00, 01 и 10. Мы также можем считать, что в самом начале оба наши замка закрыты. Тогда состояние 00 можно назвать начальным. Если же в начале оба замка открыты, то начальным состоянием будет 11. Если всј_таки нашей целью будет открыть дверь из состояния 00, то после- довательности действий AB, ABAA, AABABB приведут к успеху, а вот о последовательностях _ (ничего не делаем), ABBA и BBB такого уже сказать нельзя. Таким образом, данный конечный автомат можно ис- пользовать для классификации слов алфавита fA;Bg. Можно сказать, что слово принимается, если оно приводит к достижению цели. |