АНАЛИЗ ВЗАИМОСВЯЗИ СОДЕРЖАНИЯ МАТЕМАТИЧЕСКОЙ ТЕОРИИ МНОЖЕСТВ, ИНФОРМАТИКИ И МАТЕМАТИЧЕСКОЙ ЛОГИКИ В ПЛАНЕ РЕШЕНИЯ ЗАДАЧИ РАСПОЗНАВАНИЯ ЯЗЫКОВ КОМАНД ДЕТЕРМИНИРОВАННЫХ КОНЕЧНЫХ АВТОМАТОВ

Аннотация. Разработана усовершенствованная методика  распознавания языка  команд информационных систем, основанная на взаимной связи положений теории детерминированных конечных автоматов, математической теории множеств, теории алгоритмов, а также математической логики.

Ключевые слова: теория множеств, детерминированные конечные автоматы, теория алгоритмов, математическая логика.

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

Воспользуемся определением детерминированного конечного автомата [1] с позиции теории множеств [2], как множества M, содержащего пять элементов M = , такая что Q и Σ — в свою очередь являются конечными множествами, элемент s принадлежит множеству Q (s ∈ Q); множество F является подмножеством множества Q, либо совпадает с ним (F ⊆ Q); δ является дискретной функцией, определенной на Q и Σ, т.е. является массивом мощностью Q × Σ.

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

В плане информатики набор элементов , описывающих детерминированный конечный автомат, имеет конкретное логико-алгоритмическое выражение. Множество Σ является алфавитом автомата M, из букв которого строятся слова, набор которых образует язык команд Σ* автомата. Множество Q является множеством состояний автомата M, а элементы этого множества — его состояниями. Согласно данному выше определению автомата M в это множество входит элемент s, и следовательно, множество состояний Q не может быть пустым. Элемент s из определения M является начальным состоянием автомата M.    Множество F является множеством конечных состояний автомата M, а его элементы — конечными состояниями. Функция δ является функцией переходов.

При этом если для состояний q1 и q2, таких что q1 ∈  Q и q2 ∈  Q, можно подобрать букву a, принадлежащую алфавиту Σ (a ∈ Σ), такую, что под действие команды a автомат M переходит из состояния q1 в состояние q2 в соответствии с функцией δ, то такой переход можно записать в виде формулы теории алгоритмов вида:

q2 = δ(q1, a) .                                                                     (1)

 Возвращаясь от информатики к математике, дадим геометрическую интерпретацию простейшего детерминированного конечного автомата. Такая интерпретация  изображена на рисунке 1. Согласно ей множество состояний Q содержит два элемента q1 и q2, изображенные кружками. Начальным состояние s автомата M служит состояние q1, которое помечено треугольником слева. Множество конечных состояний F образовано единственным элементом q2, который обозначен сдвоенным кружком.

Переходы между состояниями q1 и q2 автомата M реализуются под воздействием букв a и b, образующих алфавит Σ. Переходы обозначены на схеме рис.1 изогнутыми линиями со стрелками, рядом с которыми подписана та или иная буква, являющаяся командой по осуществлению данного перехода. При этом работа автомата описывается четырьмя выражениями вида (1):

Выражения (2) — (5) позволяют записать дискретную функцию δ переходов в виде таблицы.

Таблица.— Дискретная функцию δ переходов (2) — (5) детерминированного конечного автомата M (см.: рис. 1)

Буквы алфавита Σ посредством операции конкатенции образуют слова, набор которых формирует язык Σ*. Конкатенции букв a и b формируется как слово v = ab. В свою очередь, конкатенция слов v и w формируется как слово u = vw. Несложно заметить, что изображенный на рисунке автомат М может функционировать под воздействием слов, образованных как конкатенции букв a и b. Таких слов – двухбуквенных конкатенций может быть четыре, а возможных переходов в дискретной функции δ – восемь:

Анализируемый автомат M может также функционировать также под действием трехбуквенных конкатенций вида aaa; aab; aba; abb и.т.п. Число таких конкатенций может быть восемь, а соответствующее ему количество возможных переходов в дискретной функции δ – шестнадцать.

Таким образом, алфавиту Σ, состоящему из двух букв a и b можно сопоставить язык Σ*, состоящий из однобуквенных слов a и b, двухбуквенных слов aa; ab; ba и bb, трехбуквенных слов aaa; aab; aba; abb; baa; bab; bba; и bbb и т.д. При изложенная выше задачи распознавания языка команд может быть сформулирована так. Наблюдая за переходами δ автомата M между состояниями Q под воздействием разнообразных команд и их конкатенций, необходимо установить алфавит Σ команд автомата, а также восстановить полный перечень слов языка Σ* команд, которые использованы для функционирования автомата. Подобный подход позволяет представить наблюдаемое функционирование информационной системы в виде формального непротиворечивого и полного описания этого функционирования на языке теории множеств.

Составим алгоритм наиболее употребительного способа решения подобной задачи.

Этот алгоритм основан на определениях бинарного отношения, отношения эквивалентности, теореме о разбиении множества элементов, связанных отношениями эквивалентности на фактор-множества, а также теорема Майхилла-Нероуда [3].

Бинарным         отношением         на         множестве         A          называется          [1] произвольное подмножество декартова квадрата A × A. Таким множеством может быть множество Q состояний детерминированного конечного автомата. Пусть определены состояния q0, q1 и q2 (q0 ∈ Q; q1 ∈ Q; q2 ∈ Q) автомата. Если обозначить как R высказывание о том, что состояние q0 достижимо под действием команды a из некоторого состояния q, причем состояния q1 и q2 удовлетворяют этому высказыванию в качестве q, то полагают что q1 и q2 связаны бинарным отношением R, что можно записать в виде выражения q1Rq2.

Если бинарное отношение R задано на множестве A, которому принадлежат некоторые три элемента: a, b и c (a ∈ A; b ∈ A; c ∈ A), то можно утверждать, что R рефлексивно, если имеет место высказывание aRa. Кроме того, R может быть транзитивно, если из утверждений aRb и bRc, следует высказывание aRc. Бинарное отношение R может быть симметрично, если из утверждения aRb следует утверждение bRa, а также может быть антисимметрично, если из парыв ысказываний aRb и bRa следует a = b.

Бинарное отношение называется отношением эквивалентности, если оно рефлексивно, транзитивно и симметрично. Выполнив проверку на наличие этих свойств можно также утверждать, что установленное выше на множестве множество Q состояний детерминированного конечного автомата бинарное отношение q1Rq2 является отношением эквивалентности.

Отношения эквивалентности подчиняются теореме, согласно которой, если R — отношение эквивалентности, задано на непустом множестве Q, то существует единственное множество D, именуемое фактор-множеством, такое, что, во-первых, элементами множества D являются непустые подмножества d множества D, именуемые классами эквивалентности. Во-вторых, для любых несовпадающих классов эквивалентности d1 и d2 (d1 ∈ D; d2 ∈ D; d1 ≠ d2) пересечение этих классов эквивалентности является пустым множеством: 𝑑1 ∩ 𝑑2 = ∅. В-третьих, объединение классов эквивалентности дает   исходное непустое множество Q, на котором задано отношение эквивалентности R: 𝑄= ⋃𝑑𝑖∈𝐷𝑏𝑖. И в-четвертых, для любых двух состояний детерминированного конечного автомата M утверждение о том, что любые два его состояния q1 и q2 (q1 ∈ Q; q2 ∈ Q), связанные соотношением эквивалентности R (q1Rq2), справедливо тогда и только тогда, когда для некоторого класса эквивалентности d (d ∈ D), справедливо утверждение о том, что эти состояния автомата принадлежат одному и тому же классу эквивалентности (q1 ∈ b; q2 ∈ d).

Благодаря этой теореме все состояния Q детерминированного конечного автомата могут быть разбиты на классы эквивалентности d фактор множества D, для которых справедливо одно и то же утверждение, лежащее в основе формулировки некоторого бинарного отношения R о достижимости некоторого состояния под воздействием одной и той же команды.

По отношению к подобным классам эквивалентности существует теорема Майхилла – Нероуда [3]. Если Σ* — произвольный язык некоторого конечного алфавита Σ, то справедливы два следующих утверждения. Во-первых, если язык Σ* распознается некоторым детерминированным конечным автоматом M, то число o(Σ*) элементов d фактор-множества D, то есть количество классов эквивалентности d, конечно и не превосходит числа состояний этого автомата. Во-вторых, если конечно число o(Σ*) элементов d фактор- множества D (o(Σ*) < ∞), то существует детерминированный конечный автомат M с числом состояний, равным o(Σ*), который распознает язык Σ*.

Таким образом, задача применения теории множеств к решению задачи информатики о распознавании языка Σ* команд информационной системы сводится к установлению числа o(Σ*) и анализу классов эквивалентности b фактор-множества B, определенных на бинарных отношениях эквивалентности R, сформулированных применительно к состояниям Q детерминированного конечного автомата M.

Продемонстрируем вначале классический метод [4] решения этой задачи применительно к детерминированному конечному автомату, изображенному на рис.2.

Как и автомат, изображенный на рис.1, данный автомат описывается множеством M = , где множество начальных состояний имеет вид Q = ; алфавит Σ содержит две буквы, a и b (Σ = ); начальным состоянием s является q0 (s=q0), а множество конечных состояний F представлено тремя элементами (F = ).

Следует заметить, что состояния q3 и q7 недостижимы из начального состояния q0, поэтому множества Q и F целесообразно ограничить: Q = ; F = .

Введем отношения эквивалентности R01 и R02, которые формулируются следующим образом:

R01 = «Конечное состояние автомата M достижимо из состояния q под воздействием пустого слова e, длина которого равна нулю»;

R02 = «Конечное состояние автомата M недостижимо из состояния q под воздействием пустого слова e, длина которого равна нулю».

Первому из введенных отношений эквивалентности соответствуют два состояния автомата, q0 и q2, связанные этим отношением в класс эквивалентности d01.

q0 = δ(q0, e) ,                                                                 (13)

q2 = δ(q2, e) .                                                                 (14)

Второму из введенных соотношений эквивалентности соответствуют прочие достижимые состояния автомата, q1; q4; q5 и q6, связанные этим отношением в класс эквивалентности d02.

Над элементами класса эквивалентности d02 можно задать соотношения эквивалентности R11; R12

и R13, которые формулируются следующим образом:

R11 = «Конечное состояние автомата M достижимо из состояния q под воздействием единственной буквы a,

т.е. слова, длиной в одну позицию»;

R12 = «Конечное состояние автомата M достижимо из состояния q под воздействием единственной буквы b,

т.е. слова, длиной в одну позицию»;

R13 = «Конечное состояние автомата M недостижимо из состояния q под воздействием единственной буквы, т.е. слова, длиной в одну позицию».

Отношению эквивалентности R11 соответствуют два состояния автомата, q4 и q6, связанные этим отношением в класс эквивалентности d11.

 Отношению  эквивалентности  R12  соответствует  одно  состояние     автомата эквивалентности q1,образующее класс d12.

q2 = δ(q1, b)   (17)

Соотношению эквивалентности R13 соответствует единственное из оставшихся достижимых состояний автомата из множества b02, т.е. q5, образующее класс эквивалентности d13.

Над элементом d13 класса эквивалентности d13 может быть задано соотношение эквивалентности  R21; R12; R13, R14, либо R15, которые формулируются следующим образом:

R21 = «Конечное состояние автомата M достижимо из состояния q под воздействием двухбуквенной конкатенции aа, т.е. слова, длиной в две позиции»;

R22 = «Конечное состояние автомата M достижимо из состояния q под воздействием двухбуквенной конкатенции ab, т.е. слова, длиной в две позиции»;

R23 = «Конечное состояние автомата M достижимо из состояния q под воздействием двухбуквенной конкатенции ba, т.е. слова, длиной в две позиции»;

R24 = «Конечное состояние автомата M достижимо из состояния q под воздействием двухбуквенной конкатенции bb, т.е. слова, длиной в две позиции»;

R25 = «Конечное состояние автомата M недостижимо из состояния q под воздействием двухбуквенной конкатенции, т.е. слова, длиной в две позиции».

Состояние автомата q5 соответствует отношению эквивалентности R25, что не меняет структуры классов эквивалентности, а следовательно, перебор отношений эквивалентности, формулируемых на основе трехбуквенных, четырехбуквенных и более сложных конкатенций, не влияет на структуру фактор- множества D и может быть ограничен двухбуквенной конкатенцией, рассмотренной последней.

Таким образом, использование теоремы о разбиении множества элементов, связанных отношениями эквивалентности, на классы эквивалентности позволило выделить в множестве Q состояний детерминированного конечного автомата, изображенного на рис.2, четыре элемента (o(Σ*) = 4 < ∞), фактор множества D = < d01, d11, d12, d13 >; d01=< q0, q2>; d11=< q4, q6>; d12=< q1> и d13=< q5>.

Основываясь на теореме Майхила-Нероуда [13], можно утверждать, что детерминированному конечному автомату, изображенному на рис.2, можно поставить в соответствие автомат с минимальным числом состояний Q, равным o(Σ*) = 4, и числом управляющих слов языка Σ*, также равным o(Σ*) = 4. Такой минимальный автомат изображен на рис.3.

Как и автомат, изображенный на к рис.2, данный автомат описывается множеством M = , где множество начальных состояний имеет вид Q = ; алфавит Σ содержит две буквы, a и b (Σ = ); начальным состоянием s является p0 (s=p0), а множество конечных состояний F представлено одним элементом p0 (F = ).

Несложно заметить, что функционирование данного автомата, как и автомата, изображенного на рис.2 управляется двумя однобуквенными словами – командами, a и b, а также двумя двухбуквенными словами – конкатенциями, aa и bb. При этом обе конкатенции соответствуют переходу автомата из начального состояния p0 в состояние p3:

p3 = δ(p0, aa) ,                                                                (18)

p3 = δ(p0, bb) ,                                                                (19)

а следовательно, слова-команды aa и bb, существуя в языке Σ* по отдельности, несут одинаковую смысловую информационную нагрузку.

Распознанный в результате функционирования представленного алгоритма язык Σ* описывается, таким образом, на языке теории множеств выражением: Σ*=.

Заметим, что при анализе рисунков 2 — 3 не была использована целевая дискретная функция δ переходов детерминированного конечного автомата. Покажем, что минимальная схема автомата может быть получена с помощью функции δ-1, обратной функции δ и соответствующей переходам в направлениях, обратных тем, которые изображены на рисунке 2, Эти переходы заставляют детерминированный конечный автомат перемещаться не из начального, а из конечных состояний q0 и q2, достижимых из начального состояния q0 и описаны в строках табл.2.

Обратный переход  автомата из любого из конечных состояний согласно δ-1  под  воздействием пустого слова e не влияет на его состояние, что соответствует первым двум строкам табл.2, формирующим класс эквивалентности d01.

Аналогично, обратный переход на один шаг из конечных состояний q0 и q2 возможен в состояния q0 и q2 под воздействием однобуквенного слова a, что соответствует классу эквивалентности d11. Обратный переход на один шаг из конечного состояния q2 возможен в состояние q0 и q2 под воздействием однобуквенного слова b, что соответствует классу эквивалентности d12.

И наконец, любой обратный переход на два шага из конечных состояний q0 и q2 в состояние q5 запрещен конфигурацией автомата. Зато возможны прямые переходы по четырем различающимся путям под воздействие двухбуквенных конкатенций согласно прямой целевой дискретной функции δ переходов детерминированного конечного автомата. Эти переходы соответствует классу эквивалентности d13.

Таким образом, согласно табл.2, задача распознавания языка Σ* команд информационной системы может быть решена с использованием теории множеств. При этом реализация алгоритма распознавания возможна с применением табличной формы задания целевой функции δ алгебры логики.

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

Список источников и литературы

1.         Теория автоматов / Э. А. Якубайтис,   В. О. Васюкевич,   А. Ю. Гобземис,   Н. Е. Зазнова, А. А. Курмит, А. А. Лоренц, А. Ф. Петренко, В. П. Чапенко // Теория вероятностей. Математическая статистика. Теоретическая кибернетика. — М.: ВИНИТИ, 1976. — Т. 13. — С. 109—188.

2. Ануфриенко С.А. Введение в теорию множеств и комбинаторику: Учеб. пособие. — Екатеринбург: УрГУ, 1998. — 62 с.

3. A. Nerode, «Linear automaton transformations», Proceedings of the AMS, 9 (1958), pp. 541— 544.

4. Гуц А.К. Математическая лоrика и теория алrоритмов. - Омск: Издательство Наследие. Диалог- Сибирь, 2003. — 108 с.