Реферат: Прикладная теория цифровых автоматов

Таблиця 1.6

Часткова МСА М₅

	A1	A2	A6	A17	A19	A20	A21	Ak
A0	1
A1			1
A2							1
A6					1
A17		1
A19		x1щx2				x1x2	щx1
A20				1
A21								1

На наступному етапі побудуємо об'єднану МСА М₀, в якій рядки відмічені всіма мітками А_i, крім А_k, а стовпці - всіма, крім А₀. На перетині рядка А_i і стовпця А_j запишемо формулу переходу, яка формується таким чином: F_ij=P₁f_ij¹+...+P_nf_ijⁿ (n=1...N). Де f_ijⁿ-формула переходу з вершини А_i у вершину А_j для n-ої ГСА. Наприклад, формула переходу А₀®А₁ буде мати вигляд F_0,1=щx₁щp₁щp₂щp₃+ щp₁щp₂p₃+ +p₁щp₂щp₃. У результаті ми отримаємо об'єднану МСА М₀ (табл.1.7). Ми маємо можливість мінімізувати формули переходу таким чином: розглядаючи ГСА Г₀ як ГСА Г_n, ми підставляємо певний набір P_n=1, при цьому змінні p₁..p_q не змінюють своїх значень під час проходу по ГСА. Таким чином, якщо у вершину А_i перехід завжди здійснюється при незмінному значенні p_q, то це значення p_q в рядку А_i замінимо на “1", а його інверсію на “0". Наприклад, у вершину А₃ перехід здійснюється при незмінному значенні щp₁ і щp₂, отже в рядку А₃ щp₁ і щp₂ замінимо на “1", а p₁ і p₂ на “0". У результаті отримаємо формули F_3,4=щp₃, F_3,11=p₃. Керуючись вищенаведеним методом, отримаємо мінімізовану МСА М₀ (табл.1.8).

По таблиці складемо формули переходу для об'єднаної ГСА Г₀. Формулою переходу будемо називати слідуюче вираження: A_i®F_i,1А₁+..+F_i,kА_k, де F_i,j- відповідна формула переходу з мінімізованої МСА. У нашому випадку отримаємо слідуючу систему формул:

A₀®щx₁щp₁щp₂щp₃A₁+щp₁щp₂p₃A₁+p₁щp₂щp₃A₁+x₁щx₂щp₁щp₂щp₃A₂+x₁x₂щp₁щp₂щp₃A₃+

+щx₁щp₁p₂p_3­A₈+x₁щp₁p₂p₃A₁₃+щp₁p₂щp₃A₁₄

A₁®щp₁щp₃A_2­+p₁щp₃A₆+щp₁p₃A₇

A₂®щp₁щp₂щp₃A₆+щp₁p₂p₃A₁₈+p₁щp₂p₃A₂₁

A₃®щp₃A₄+p₃A₁₁