Едыгаров И.А.
ХРОНОЛОГИЯ РАЗВИТИЯ ТЕОРИИ АВТОМАТОВ, ФОРМАЛЬНЫХ ЯЗЫКОВ И ВЫЧИСЛЕНИЙ *
Аннотация:
в статье приведена хронология развития теории автоматов от начала прошлого века до настоящего времени. Приведены основные авторы
Ключевые слова:
теория автоматов, формальные языки, теория алгоритмов, структура, автоматная структура
УДК 517.713.32
Едыгаров И.А.
старший преподаватель кафедры прочности конструкции (ПК)
Казанский национальный исследовательский технический университет
(г. Казань, Россия)
ХРОНОЛОГИЯ РАЗВИТИЯ ТЕОРИИ АВТОМАТОВ,
ФОРМАЛЬНЫХ ЯЗЫКОВ И ВЫЧИСЛЕНИЙ
Аннотация: в статье приведена хронология развития теории автоматов от начала прошлого века до настоящего времени. Приведены основные авторы.
Ключевые слова: теория автоматов, формальные языки, теория алгоритмов, структура, автоматная структура.
Теория автоматов — это раздел теории формальных языков и вычислений, который изучает математические модели вычислительных процессов и типы автоматов. Истоки восходят к Давиду Гильберту, а современным основателями этого направления считаются Анил Нероде и Бахадыр Хусаинов.
В 1900 году Дэвид Хильберт выдвинул проблему описания формального языка, который можно было бы использовать для описания всех математических утверждений.
И в 1936 год Алан Тьюринг опубликовал статью "О вычислимых числах с применением к Entscheidungsproblem", в которой была представлена концепция машины Тьюринга, основы теории автоматов. Также определил, что любая вычислимая функция может быть вычислена с помощью универсальной машины Тьюринга. Позже, машина Тьюринга с конечным объёмом памяти эквивалентна конечным автоматам.
1943-1944 годы: Уоррен Маккаллок и Уолтер Питтс предложили формальную модель искусственных нейронных сетей, которая стала отправной точкой для развития теории автоматов.
В 1949 году Клаус Грёбнер представил теорию автоматов и формальных языков.
1956 год: Стивен Клини (Stephen Kleene) предложил концепцию регулярных выражений, которая стала фундаментом для теории автоматов и формальных языков. В этом же году Джон Маккарти создал язык программирования Lisp, который стал первым языком программирования, использующим рекурсию и рекурсивные функции.
1959 год: Майкл Рабин и Дэна Скотт предложили концепцию конечных автоматов, которая стала важным шагом в развитии теории автоматов и формальных языков. В этом же Ноам Хомский опубликовал свою теорию формальных грамматик, которая была основана на работе Грёбнера.
1960-е годы: Ноам Хомский предложил иерархию Хомского, классификацию формальных грамматик и языков на основе их выразительной мощности. Это стало важным дополнением к теории автоматов.
1963 год: Марвин Минский опубликовал книгу "Компьютеры и мозг: фундаментальные принципы кибернетики", которая стала основой теории автоматов и кибернетики.
1965 год: Дональд Кнут опубликовал свою классическую книгу "The Art of Computer Programming", которая существенно повлияла на развитие теории алгоритмических структур и формальных языков.
В 1970 году Эдсгер Дейкстра опубликовал свою теорию параллельного программирования, которая стала основой для создания многопоточных программ. Исследования в области теории автоматов продолжают развиваться. В этот период возникает понятие "семейства автоматных структур", которое позволяет обобщить и систематизировать результаты исследований.
1971 год: Майкл О. Рабин и Дэна Скотт опубликовали статью "Деревья, автоматы и игры", которая объединила различные подходы к теории автоматов.
В 1973 году Джон Хопкрофт и Джеффри Ульман опубликовали свою работу по теорию автоматов и формальных языков, которая стала основой для создания современных компиляторов и интерпретаторов.
1980-е годы: Развитие теории автоматов продолжается в связи с ростом интереса к обработке естественного языка, распознаванию образов, компьютерной графике и машинному обучению. Ричард Карп опубликовал свою теорию сложности вычислений, которая стала основой для создания алгоритмов, использующихся в современных компьютерах. Теория автоматных структур находит широкое применение в области компиляции, синтаксического анализа и других аспектах компьютерных наук.
1990-е годы: Исследование автоматов с бесконечными структурами, например, теория ω-автоматов, автоматов Бюхи и Мюллера.
2000-е годы и настоящее время: продолжается развитие и применение теории автоматов в различных областях, таких как формальные методы верификации, теория игр, криптография, сетевые протоколы и биоинформатика. Работа Б. Хуссейнова и А. Нерода "Теория автоматов и ее приложения" — это всеобъемлющий ресурс, который углубляется в теорию конечных автоматов на конечных строках, бесконечных строках и деревьях. Авторы эффективно использовали работы Майхилла и Нерода о конечных классах смежности на строках для представления концепций ясным и кратким образом.
Теория автоматов развивается и находит все больше практических применений, поскольку автоматы являются универсальными моделями для анализа и синтеза различных вычислительных процессов.
СПИСОК ЛИТЕРАТУРЫ:
Номер журнала Вестник науки №12 (69) том 5 ч. 2
Ссылка для цитирования:
Едыгаров И.А. ХРОНОЛОГИЯ РАЗВИТИЯ ТЕОРИИ АВТОМАТОВ, ФОРМАЛЬНЫХ ЯЗЫКОВ И ВЫЧИСЛЕНИЙ // Вестник науки №12 (69) том 5 ч. 2. С. 159 - 162. 2023 г. ISSN 2712-8849 // Электронный ресурс: https://www.вестник-науки.рф/article/12172 (дата обращения: 19.05.2024 г.)
Вестник науки СМИ ЭЛ № ФС 77 - 84401 © 2023. 16+