The 14 reference contexts in paper B. Bychkov I., V. Gurenko V., Б. Бычков И., В. Гуренко В. (2016) “Анализ структур данных для представления базовых моделей конечных автоматов // Data Structure Analysis to Represent Basic Models of Finite State Automation” / spz:neicon:technomag:y:2015:i:2:p:150-168

  1. Start
    2461
    Prefix
    В литературе, посвященной теории автоматов, основное внимание уделено двум аспектам. Во-первых, формальному описанию автоматов с последующим решением традиционных задач теории автоматов, включая задачи анализа и синтеза
    Exact
    [1-4]
    Suffix
    . Во-вторых, практическому приложению автоматов в различных областях, в том числе находящихся на стыке традиционных научных направлений и даже за пределами области технических наук. Так, аппарат теории автоматов успешно применяется в прикладных задачах математической лингвистики, биоинформатики, теории алгоритмов, теории формальных систем, криптологии и других.
    (check this in PDF content)

  2. Start
    4884
    Prefix
    Проверить экспериментально полученные результаты и сделать вывод о предпочтении той или иной структуры в зависимости от решаемой задачи теории автоматов. 1. Варианты структур данных Под базовыми моделями КА традиционно понимают автоматы Мили и Мура
    Exact
    [1-4]
    Suffix
    , причем обе модели описывают детерминированные КА [1]. Такой автомат считают заданным, если определены следующие его компоненты: – множества X и Y входного и выходного алфавита КА; – множество S состояний автомата; – начальное состояние s0; – однозначная функция переходов f и функция выходов g.
    (check this in PDF content)

  3. Start
    4942
    Prefix
    Проверить экспериментально полученные результаты и сделать вывод о предпочтении той или иной структуры в зависимости от решаемой задачи теории автоматов. 1. Варианты структур данных Под базовыми моделями КА традиционно понимают автоматы Мили и Мура [1-4], причем обе модели описывают детерминированные КА
    Exact
    [1]
    Suffix
    . Такой автомат считают заданным, если определены следующие его компоненты: – множества X и Y входного и выходного алфавита КА; – множество S состояний автомата; – начальное состояние s0; – однозначная функция переходов f и функция выходов g.
    (check this in PDF content)

  4. Start
    6308
    Prefix
    Задание начального состояния s0 также тривиально. Таким образом, задача машинного представления КА сводится к поиску оптимальных структур данных для представления функции переходов f и функции выходов g. Из ряда возможных вариантов
    Exact
    [1-4]
    Suffix
    рассмотрим следующие: 1) таблица переходов/выходов; 2) матрица соединений; 3) взвешенный ориентированный граф переходов КА. Существуют и другие способы задания КА. Например, конечный автоматраспознаватель может быть задан синтаксической диаграммой.
    (check this in PDF content)

  5. Start
    6824
    Prefix
    Однако этот вариант выходит за рамки настоящей работы, поскольку базовые модели КА являются преобразователями, а не распознающими автоматами. Из всего многообразия структур данных, широко рассмотренных в литературе (см.
    Exact
    [5-9]
    Suffix
    ), для представления КА указанными выше способами наиболее подходят статические структуры в виде многомерных массивов и матриц, а также динамические в виде списков различной связности.
    (check this in PDF content)

  6. Start
    7683
    Prefix
    Этого достигают, например, за счет создания локальных непрерывных участков данных с указателями (так называемых «пулов»), которые целиком помещают в кэш-память, и дальнейшего соединения их в цепочки. При этом для экономии памяти и сокращения времени адресации указатели внутри и вне пула могут иметь разную длину
    Exact
    [10]
    Suffix
    . Рассмотрим первый из трех обозначенных способов представления КА – таблицу переходов/выходов. Приемлемым вариантом ее представления статической структурой данных является многомерный массив: трехмерный в случае КА Мили и двумерный (прямоугольная матрица) в случае КА Мура.
    (check this in PDF content)

  7. Start
    9279
    Prefix
    Таблица переходов/выходов КА Мили в виде: a – статического трехмерного массива; б – двухуровневого вектора Айлифа a б Рис. 2. Таблица переходов/выходов КА Мура в виде: a – статической матрицы; б – двухуровневого вектора Айлифа Для представления матрицы соединений КА
    Exact
    [2]
    Suffix
    можно использовать сходные структуры данных, однако каждым элементом такой матрицы является список. Поэтому для организации статической и динамической структур следует применить, соответственно, матрицу списков и трехуровневый вектор Айлифа.
    (check this in PDF content)

  8. Start
    9776
    Prefix
    Вид названных структур для КА Мили показан на рис. 3 1 . a б Рис. 3. Матрица соединений КА Мили в виде: а – матрицы списков; б – трехуровневого вектора Айлифа Взвешенный орграф переходов КА
    Exact
    [1, 2]
    Suffix
    можно задать любой структурой данных, разработанной или адаптированной для представления графовых моделей [11-14]. Традиционные для графов статические структуры – матрицу смежности и матрицу инциденций нельзя признать оптимальными с точки зрения машинной реализации, поскольку компенсацией за их простоту и наглядность, как правило, является сильная разр
    (check this in PDF content)

  9. Start
    9905
    Prefix
    Матрица соединений КА Мили в виде: а – матрицы списков; б – трехуровневого вектора Айлифа Взвешенный орграф переходов КА [1, 2] можно задать любой структурой данных, разработанной или адаптированной для представления графовых моделей
    Exact
    [11-14]
    Suffix
    . Традиционные для графов статические структуры – матрицу смежности и матрицу инциденций нельзя признать оптимальными с точки зрения машинной реализации, поскольку компенсацией за их простоту и наглядность, как правило, является сильная разреженность, что увеличивает и емкостную, и временную сложность.
    (check this in PDF content)

  10. Start
    12484
    Prefix
    Для сравнения структур данных уместно применить оценку вычислительной сложности в емкостной и временной составляющих. При этом емкостная сложность даст оценку объема памяти, занимаемого структурой, а временная – времени выполнения алгоритмов конкретных операций над КА с использованием данной структуры
    Exact
    [15]
    Suffix
    . Таким образом, в качестве первого критерия оценки машинных структур представления КА следует принять память, отводимую под хранение структуры данных. Заметим, что объем памяти, требуемый для решения самих задач теории автоматов, характеризует алгоритмы, а не структуры данных и потому критерием оценки являться не должен.
    (check this in PDF content)

  11. Start
    13071
    Prefix
    Рассмотрим, время выполнения каких операций существенно при решении каждой из обозначенных задач. Будем считать, что для работы с машинным представлением КА используются известные алгоритмы задач теории автоматов, описанные, например, в
    Exact
    [1- 4]
    Suffix
    . Задача эквивалентных преобразований. Алгоритм преобразования КА Мура в КА Мили в случае представления автомата графом переходов предусматривает перенесение выходного сигнала, соответствующего каждой вершине, на все дуги, входящие в эту вершину [1].
    (check this in PDF content)

  12. Start
    13340
    Prefix
    Алгоритм преобразования КА Мура в КА Мили в случае представления автомата графом переходов предусматривает перенесение выходного сигнала, соответствующего каждой вершине, на все дуги, входящие в эту вершину
    Exact
    [1]
    Suffix
    . При этом значение нужного выходного сигнала извлекают из таблицы соответствия состояний и выходных сигналов, которую следует сформировать до начала обхода графа. Обратное преобразование КА Мили в КА Мура подразумевает поиск пар «состояние – выходной сигнал», приводящих к переходу автомата в новое состояние.
    (check this in PDF content)

  13. Start
    13902
    Prefix
    При этом происходит перебор всех возможных переходов КА с извлечением для каждого из них информации об инициирующем его входном сигнале и о вырабатываемом на переходе выходном сигнале. Подробно данный алгоритм изложен в
    Exact
    [1, 2]
    Suffix
    . Основываясь на алгоритмах преобразования базовых моделей КА, можно выделить два временных критерия оценки структур данных: время формирования таблицы соответствия состояний и выходных сигналов КА Мура и время полного перебора переходов КА Мили с получением для каждого перехода начального и конечного состояний, входного и выходного сигналов.
    (check this in PDF content)

  14. Start
    15094
    Prefix
    Отметим, что время поиска всех недостижимых состояний эквивалентно времени полного перебора переходов. Те же критерии следует выделить и для задачи определения изоморфизма КА. Задача минимизации КА. Алгоритм минимизации детально разобран в
    Exact
    [1]
    Suffix
    . Он также предусматривает полный обход графа переходов автомата. Для решения этой задачи не требуется выполнения каких-либо действий со структурой данных, неучтенных при рассмотрении предыдущих задач.
    (check this in PDF content)