ого символу і поточного стану. Така зміна стану називається переходом. При переході може виявитися, що новий стан збігається зі старим.
Роботу автомата можна описати математично за допомогою функції переходів, яка по поточному стану та поточного вхідного символу дає новий стан автомата. Символічно ця залежність описується так:.
Враховуючи, що стану «чет» і «нечет» означають відповідно, парне і непарне кількість прочитаних одиниць, визначимо функцію переходів контролера непарності наступним чином:
Ця функція переходів відображає той факт, що парність змінюється тоді і тільки тоді, коли на вході читається одиниця.
Деякі стани автомата вибираються як допускають, або заключних. Якщо автомат, почавши роботу в початковому стані, при прочитанні всього ланцюжка переходить в одне з допускають станів, то говорять, що цей ланцюжок допускається автоматом. Якщо останній стан автомата не є допускає, то говорять, що автомат відкидає ланцюжок. Контролер непарності має єдине допускає стан - «Непара».
Перехід автомата зі стану в стан при читанні вхідного символу Х будемо наочно зображати так:. Наприклад, для контролера непарності можна написати:. Аналогічним чином можна зобразити послідовність переходів:
Ця запис показує, як автомат в стані «Чет» застосовується до ланцюжку «1101». Вхідну ланцюжок «101» автомат відкидає, тому що вона переводить його з початкового стану в стан, що не є допускачем. Символічно це зображується так:.
Контролер непарності розпізнає безліч ланцюжків, що складаються з нулів і одиниць, і що містить непарне число одиниць. Безліч всіх ланцюжків, які розпізнаються кінцевим автоматом, називається регулярним безліччю.
Один із зручних способів подання кінцевих автоматів - це таблиця переходів. Для контролера непарності така таблиця виглядає наступним чином:
01ЧЕТЧЕТНЕЧЕТ0НЕЧЕТНЕЧЕТЧЕТ1
Інформація в таблиці переходів розміщується у відповідності з наступними угодами:
Стовпці позначені вхідними символами;
Рядки позначені символами станів;
Елементами таблиці є символи нових станів, відповідних вхідним символам стовпців і станам рядків;
Перший рядок позначена символом початкового стану;
Рядки, відповідні допускає (заключною) станам, позначені праворуч одиницями, а рядки, відповідні отвергающим станам, позначені праворуч нулями.
Таким чином, наведена таблиця переходів задає кінцевий автомат, у якого:
Вхідний безліч={0,1};
Безліч станів={чіт, непарне};
Функції переходів:
Початковий стан={Чет};
Допускають стану={Непара}.
Найпростіша програмна реалізація КА - контролера непарності:
# include «stdafx.h»
# include «iostream.h»
# include «stdio.h»
# include «conio.h» per (int tsost, char tsymb)
{int slsost; (tsymb)
{case «0»: if (tsost == 0) slsost=0; else slsost=1; «1»: if (tsost == 1) slsost=0; else slsost=1;} slsost;
}; main ()
{int i, kol, tsost, slsost; ch, inpstr [80]; («ENTER STRING»);=0;
while ((ch=getch ())!=13 && i <80) / /???? ?? ?????? ???????
{putch (ch); [i +...
