Синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции
Електронний архів E-archive DonNTU – (Electronic archive Donetsk National Technical University)
Переглянути архів Інформація| Поле | Співвідношення | |
| Title |
Синтез регулярного выражения языка, порожденного помеченным графом, методом его локальной редукции
|
|
| Creator |
Ногина, Н.В.
Грунский, И.С. Nogina, N.V. Grunskiy, I.S. |
|
| Subject |
помеченный граф
алгебра языка регулярное выражение локальная редукция графа labeled graphs algebra of language regular expression local reduction of the graph |
|
| Description |
New algorithm for analysis of languages generated by graphs with labeled vertices and transitions is proposed. It gives regular expression (in terms of the proper algebra) describing the language. The algorithm is based on a local reduction of the graph, that is the sequential exclusion of vertices and transitions. It is proposed a reduction procedure, in which removal starting at the final vertex to initial, and a simplification of the graph in the process of reduction, which often reduces the amount of computations. Предлагается новый алгоритм анализа языков, порожденных графами с помеченными вершинами и дугами. Он позволяет находить алгебраическое выражение (в терминах соответствующей алгебры) таких языков. Алгоритм основан на локальной редукции графа, т.е. на последовательном исключении его вершин и дуг. Предложен порядок редукции, при котором исключение вершин проводится от финальной к начальной, а также упрощение графа в процессе редукции, что зачастую позволяет уменьшить объем вычислений. |
|
| Date |
2013-04-24T19:40:10Z
2013-04-24T19:40:10Z 2012 |
|
| Identifier |
УДК 519.713
http://ea.donntu.edu.ua/handle/123456789/19229 |
|