Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Определяем условно совместимые состояния




Определение абсолютно совместимых состояний без дополнительных условий.

Такими состояниями называются состояния, у которых при воздействии одного и того же слова xi Î X осуществляется переход в одинаковые состояния si Î S.

Если переход в состояние при воздействии входного сигнала не определен, то на основании допустимости входных слов считаем, что состояния, в которые переходит автомат, совпадают.

Сравним состояния s1 с s2 по таблице переходов (см. табл. 1).

x1 => s2 и s3 - состояния не совпадают;

x2 => -/- и s5 - состояния допустимо совпадают;

x3 => s3 и s2 - состояния не совпадают;

x4 => s2 и -/- - состояния допустимо совпадают.

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

При сравнении состояний s1 и s3 нетрудно видеть, что и они не относятся к абсолютно совместимым состояниям без дополнительных условий.

Вместе с тем, при сравнении состояний s3 и s5 видно, что при

x1 => s3 и -/- - состояния допустимо совпадают;

x2 => s4 и -/- - состояния допустимо совпадают;

x3 => -/- и s1 - состояния допустимо совпадают;

x4 => s5 и -/- - состояния допустимо совпадают.

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

В треугольной матрице в ячейке на пересечении состояний s3 и s5 ставиться V (птичка).

Из дальнейшего сравнения состояний видно, что больше абсолютно совместимых состояний нет.

 

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

Сравним состояния s1 и s2 по таблице переходов (см. табл. 1).

x1 => s2 и s3 - состояния не совпадают;

x2 => -/- и s5 - состояния допустимо совпадают;

x3 => s3 и s2 - состояния не совпадают;

x4 => s2 и -/- - состояния допустимо совпадают.

Из сравнения видно, что отличия состоят при воздействии входных сигналов x1 и x3. Следовательно, состояния s1 и s2 считаются совместимыми при условии, что совместимы состояния s2 и s3 (на основании симметричности s2 ~ s3 => s3 ~ s2). Поэтому в треугольной матрице в ячейке на пересечении состояний s1 и s2 записываем условия совместимости в виде 2.3.

Сравниваем состояния s1 и s3 .

x1 => s2 и s3 - состояния не совпадают;

x2 => -/- и s4 - состояния допустимо совпадают;

x3 => s3 и -/- - состояния допустимо совпадают;

x4 => s2 и s5 - состояния не совпадают.

Из сравнения видно, что не совпадают состояния при x1 (s2, s3) и x4 (s2, s5). Следовательно, состояния s1 и s3 совместимы при условии, что совместимы состояния (s2 и s3) и (s2 и s5). В треугольной матрице в ячейке на пересечении состояний s1 и s3 записываем условия совместимости в виде 2.3 и 2.5.

Продолжая дальнейшее сравнение состояний, заполняются все ячейки треугольной матрицы, вид которой представлен в таблице 5.

Таблица 5

s2 2.3      
s3 2.3 2.5 4.5    
s4 2.3 1.5 1.4  
s5 1.3 Х V 1.2
  s1 s2 s3 s4

 

 

Дальнейшее определение совместимых и несовместимых состояний осуществляется из анализа таблицы 5 путем последовательного просмотра столбцов.

Шаг 1. Находятся абсолютно несовместимые состояния. В данном случае это состояния (s2 и s5). Просматривая столбцы треугольной матрицы и в тех ячейках, где имеются сочетания состояний s2 и s5 (2.5) ставиться Х (крест).

В результате получим таблицу 6.

 

Таблица 6

s2 2.3      
s3 2.3 2.5Х 4.5    
s4 2.3 1.5 1.4  
s5 1.3 Х V 1.2
  s1 s2 s3 s4

Так как состояние (s 2 и s 5) несовместимы, следовательно, несовместимы состояния (s 1 и s 3) по условию совместимости.

Шаг 2. Просматривая столбцы треугольной матрицы таблицы 6, там, где в ячейках есть сочетание состояний (s 1 и s 3) ставиться Х (крест). На основании условий совместимости несовместимыми состояниями являются состояния (s 1 и s 5).

В результате получим таблицу 7.

 

Таблица 7

s2 2.3      
s3 2.3 2.5Х 4.5    
s4 2.3 1.5Х 1.4  
s5 1.3Х Х V 1.2
  s1 s2 s3 s4

Шаг 3. Просматривая таблицу 7, там где в ячейках есть сочетание состояний (s1 и s5) ставиться Х (крест). Несовместимыми состояниями будут состояния (s2 и s4).

Эта процедура проводится для всех клеток, отмеченных крестом, и заканчивается тогда, когда таких клеток не остаётся. В этом случае клетки без крестов соответствуют совместимым парам состояний, а клетки с крестами – несовместимым.

В результате исключения несовместимых состояний получим треугольную матрицу совместимых состояний.

После применения этой процедуры к треугольной таблице рассматриваемого примера, получаем следующий результат:

пары состояний (1, 2), (1, 4), (2, 3), (3, 4), (3, 5), (4, 5) совместимы;

пары состояний (1,3), (1, 5), (2, 4), (2, 5) не совместимы.

Будем говорить, что множество полученных состояний В (В Î А) совместимо с состоянием sm Î A (обозначение sm ~В), если sm ~ sn для любого sn Î В.




Поделиться с друзьями:


Дата добавления: 2015-07-02; Просмотров: 624; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.014 сек.