Методы распознавания автоматов по их геометрическим образам

Теория автоматов занимается изучением абстрактных вычислительных устройств, или «машин» . В 1930-е годы, задолго до появления компьютеров, А. Тьюринг исследовал абстрактную машину, которая, по крайней мере, в области вычислений, обладала всеми возможностями современных вычислительных машин. Сам автомат – это формальная модель, которая описывает поведение некоторой системы. В 1940-х и 1950-х годах немало исследователей занималось изучением простейших машин, которые называются конечными автоматами, формальное определение которого будет дано далее. Такие автоматы вначале были предложены в качестве модели функционирования головного мозга человека. Однако вскоре оказалось, что данная модель не применима для описания функционирования головного мозга, но была более полезна для множества других целей.

---

Если вам нужна докторская диссертация на заказ в Ростове переходите на сайт Work5.

---

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

Как видно из приведенного обзора, задача распознавания является актуальной. Используются различные экспериментальные подходы исходя из поставленной задачи. Различные формы представления автомата позволяет работать в удобном для нас формате: таблицы, графы или матрицы. Выбор того или иного представления обусловлен не только человеческим фактором, но и потенциальной возможностью применения данной модели в компьютерном представлении, что, безусловно, выгодным является представление в виде матриц. В дальнейшем планируется более подробно изучить экспериментальные подходы в распознавании автоматов. Покажем на примере возможность использования конечных автоматов (КА) для решения различных задач разбора. Все дело в том, что программисты очень часто сталкиваются с проблемой разделения строк на некоторые осмысленные части, проверки правильности ввода значений и т.д. В принципе, так как очень часто пользователем является человек, то самым естественным для него путем передачи информации будет человеческая речь. Тем не менее, задача выделения смысла из человеческой речи до сих пор не решена (и, вообще-то, вряд ли будет решена в ближайшем будущем). Поэтому для подобных случаев используется формальные описания некоторых структур - формальные грамматики. Этот раздел информатики является частью более общего - формальных методов. Заданная грамматика позволяет указать, какая строка символов принадлежит некоторому множеству, а какая --- нет. Можно привести пример с множеством корректных URL-адресов: грамматика, заданная соответствующим RFC, указывает на то, какие строки являются правильными URL-адресами, а какие - нет. Для некоторых типов грамматик существуют соответствующие им алгоритмы разбора строк символов, именно этим и хорошо применение грамматик. Конечные автоматы применяются для простейших грамматик, но зачастую этого хватает. Обычно КА применятся для того, что называется лексическим анализом, т.е. для разбиения исходной строки на набор некоторых лексических единиц (например, выделение из текста слов и чисел).

1. Хопкрофт Д., Мотваин Р., Ульман Д.Д. Введение в теорию автоматов, языков и вычислений, 2-е изд.: Пер. с англ. – М.: Издательский дом «Вильямс», 2002. – 528с. 2. Грунский И.С. Анализ поведения конечных автоматов, ИПММ НАН Украины, Луганский государственный педагогический университет. – Луганск: Издательство Луганск. гос. дед. Ун-та, 2003. – 318 с. 3. Агибалов Г.П. Лекции по теории конечных автоматов / Агибалов Г.П., Оранов А.М. – Томск: Изд-во Томск.ун-та, 1984. – 185с. 4. Громов М.Л., Кондратьева О.В. Об одном классе автоматов с полиномиальной оценкой числа состояний в наблюдаемой форме, Журн. СФУ. Сер. Матем. и физ., 1:3. - 2008, 257–261сс. 5. Поспелов А.Д. Логические методы анализа и синтеза схем, М., «Энергия», 1974, сс. 10 – 158 6. Закревский А.Д, Поттосин Ю.В., Черемисинова Л.Д. Основы логического проектирования. Кн. 2 Оптимизация в булевом пространстве. – Минск: ОИПИ НАН Беларуси, 2006.-254с. 7. Гилл А. Введение в теорию конечных автоматов. – Наука, - М., 1966 8. Лекции по теории автоматов - http://www.studfiles.ru/dir/cat40/subj463/file13976/view129998/page20.html [Электронный ресурс], режим доступа - свободный