- 1
- 2
- 3
- 4
- 5
- . . .
- последняя »
большую проблему.
Создание программ со сложным поведением без использования диаграмм приводит к трудностям на всех этапах жизненного цикла. Особенно сложно в этом случае реализовывать программы, так как все особенности их поведения приходится держать в голове в течение всего времени их написания, вместо того чтобы отобразить их на диаграмме и на время забыть. Еще одним преимуществом автоматных программ является простота внесения изменений в них специалистами в предметной области, не являющимися профессиональными программистами.
Следующее преимущество автоматного подхода - эффективность верификации автоматных программ на основе метода Model Checking (верификация на модели). Это объясняется тем, что модель для верификации программ этого класса может строиться автоматически по графу переходов и иметь относительно небольшой размер, так как в графах переходов используются только управляющие состояния.
Для автоматных программ отсутствует семантический разрыв между требованиями к программе и к модели, так как он устраняется в ходе разработки графов переходов на этапе проектирования. Это позволяет считать автоматные программы приспособленными к верификации. Таким образом, при верификации программ имеет место ситуация, аналогичная с контролем схем со сложной логикой - эти схемы не удается проверить, если они не спроектированы специальным образом для обеспечения контролепригодности.
1.2 Понятия конечного автоматаКонечный автомат - абстрактный автомат без выходного потока, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию.
Существуют различные варианты задания конечного автомата. Например, конечный автомат может быть задан с помощью пяти параметров: (1) где: - конечное множество состояний автомата;- начальное (стартовое) состояние автомата ();
множество заключительных (или допускающих) состояний, таких что ;
Σ - допустимый входной алфавит (конечное множество допустимых входных символов), из которого формируются строки, считываемые автоматом;
δ - заданное отображение множестваво множествоподмножеств Q: (2) (иногда δ называют функцией переходов автомата).
Автомат начинает работу в состоянии q0, считывая по одному символу входной строки. Считанный символ переводит автомат в новое состояние из Q в соответствии с функцией переходов. Если по завершении считывания входного слова (цепочки символов) автомат оказывается в одном из допускающих состояний, то слово "принимается" автоматом. В этом случае говорят, что оно принадлежит языку данного автомата. В противном случае слово "отвергается".
Конечные автоматы широко используются на практике, например в синтаксических, лексических анализаторах, и тестировании программного обеспечения на основе моделей.
Другие способы описания
Диаграмма состояний (или иногда граф переходов) - графическое представление множества состояний и функции переходов. Представляет собой нагруженный однонаправленный граф, вершины которого - состояния КА, ребра - переходы из одного состояния в другое, а нагрузка - символы, при которых осуществляется данный переход. Если переход из состояния q1 в q2 может быть осуществлен при появлении одного из нескольких символов, то над дугой диаграммы (ветвью
- 1
- 2
- 3
- 4
- 5
- . . .
- последняя »
Похожие работы
Интересная статья: Быстрое написание курсовой работы