крайни автомати

Машината за състояние (наричан SC) - резюме на компютърно устройство с фиксиран и ограничен размер на паметта, която се чете на входа на веригата (последователност от символи на азбука) и изхода казва, че те принадлежат към множество от които е изградена за разпознаване.

Принципът на работа на държавните машини от различни нива се използва широко в компютърни устройства, както в хардуер и софтуер в нива: съставителите, преводачи програми, различни енкодери, антивирусен софтуер и т.н. По принцип работата на всяка програма може да бъде представен като работата на верига от държавни машини с различна сложност. Помислете за изграждане на прост CA - разпознаване на. Следните параметри трябва да се определят по време на строителството на такъв краен автомат на:

а) въвеждане азбука V краен автомат (ограничен набор на входящи символи, които ще признае, Калифорния);

б) ограничен набор от държави S;

в) първоначалното състояние на АС - s0 (състояние, от което космически кораб започва обработката на нова верига);

г) множество приемащи държави - Sdop (подгрупата на състояния, които се сравнява с елементите на НС достигнал състояние след присъединяването "края на верига" символ);

д) преход маса (контрол на маса), който е един чифт "текущото състояние - входен символ" задава ново състояние на космическия кораб от серия S на състояния).

1 комплект от входни символи задължително да включва специален символ "край на веригата", която разказва на космическия кораб, който достига до състояние SI за сравнение с елементите на Sdop и ако си Î Sdop. прескачане веригата; в противен случай веригата се отхвърля. В текста на този герой ще изглежда така - |.

SC винаги започва от първоначалното състояние s0. Символи разпознаваем знак по знак низ, получени от първо и промененото състояние космически кораб в съответствие с таблицата за скок. След получаване на "края на веригата" символ автоматично се постигне състояние е фиксиран и в сравнение с набор от приемащи държави. Въз основа на това сравнение, веригата се допуска или отказва. В действителност на космическия кораб действа като филтър, който пропуска "правото" на веригата. Друго тълкуване на НС - компактен алгоритъм за разпознаване на редовен, включително определя безкраен, които се изграждат на програмиста да кодира началото на (изпълнението на алгоритъма в даден език за програмиране).

Строителство космически кораб да се признае, предварително определен набор от струни - творчески процес и спорна. Теоретично, да се признае един и същ набор от низове, може да се изгради един безкраен брой на сателити. Горният принцип не е приложим за разпознаване на всеки редовен набор. Той е ефективен при следните случаи:

- разпознаваеми вериги съдържат определени комбинации от символи в началото, края, или (II) средата на веригата;

- разпознаваеми вериги съдържат ограничен брой повторения на определени символи или комбинация от тях (не повече от п; точно п, където п е не по-малко от п = 1,2,3.);

- разпознаваеми вериги съдържат забрана на определени комбинации от символи в началото или в края (и) във веригата;

- разпознаваемите вериги съдържат комбинации от горните ограничения. (За повече подробности - виж DM лекция.).