The Determining Finite Automata Process
The theory of formal languages widely uses finite state automata both in implementation of automata-based approach to programming, and in synthesis of logical control algorithms.To ensure unambiguous operation of the algorithms, the synthesized finite state automata must be deterministic. Within the...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
MGTU im. N.È. Baumana
2017-09-01
|
| Series: | Matematika i Matematičeskoe Modelirovanie |
| Subjects: | |
| Online Access: | https://www.mathmelpub.ru/jour/article/view/67 |
| _version_ | 1818483355600027648 |
|---|---|
| author | M. S. Vinogradova S. B. Tkachev I. E. Kandaurova |
| author_facet | M. S. Vinogradova S. B. Tkachev I. E. Kandaurova |
| author_sort | M. S. Vinogradova |
| collection | DOAJ |
| description | The theory of formal languages widely uses finite state automata both in implementation of automata-based approach to programming, and in synthesis of logical control algorithms.To ensure unambiguous operation of the algorithms, the synthesized finite state automata must be deterministic. Within the approach to the synthesis of the mobile robot controls, for example, based on the theory of formal languages, there are problems concerning the construction of various finite automata, but such finite automata, as a rule, will not be deterministic. The algorithm of determinization can be applied to the finite automata, as specified, in various ways. The basic ideas of the algorithm of determinization can be most simply explained using the representations of a finite automaton in the form of a weighted directed graph.The paper deals with finite automata represented as weighted directed graphs, and discusses in detail the procedure for determining the finite automata represented in this way. Gives a detailed description of the algorithm for determining finite automata. A large number of examples illustrate a capability of the determinization algorithm. |
| first_indexed | 2024-12-10T12:59:02Z |
| format | Article |
| id | doaj.art-2d69ea42386345028427db102411a2ef |
| institution | Directory Open Access Journal |
| issn | 2412-5911 |
| language | Russian |
| last_indexed | 2024-12-10T12:59:02Z |
| publishDate | 2017-09-01 |
| publisher | MGTU im. N.È. Baumana |
| record_format | Article |
| series | Matematika i Matematičeskoe Modelirovanie |
| spelling | doaj.art-2d69ea42386345028427db102411a2ef2022-12-22T01:48:00ZrusMGTU im. N.È. BaumanaMatematika i Matematičeskoe Modelirovanie2412-59112017-09-010411710.24108/mathm.0417.000006772The Determining Finite Automata ProcessM. S. Vinogradova0S. B. Tkachev1I. E. Kandaurova2Bauman Moscow State Technical University, MoscowBauman Moscow State Technical University, MoscowBauman Moscow State Technical University, MoscowThe theory of formal languages widely uses finite state automata both in implementation of automata-based approach to programming, and in synthesis of logical control algorithms.To ensure unambiguous operation of the algorithms, the synthesized finite state automata must be deterministic. Within the approach to the synthesis of the mobile robot controls, for example, based on the theory of formal languages, there are problems concerning the construction of various finite automata, but such finite automata, as a rule, will not be deterministic. The algorithm of determinization can be applied to the finite automata, as specified, in various ways. The basic ideas of the algorithm of determinization can be most simply explained using the representations of a finite automaton in the form of a weighted directed graph.The paper deals with finite automata represented as weighted directed graphs, and discusses in detail the procedure for determining the finite automata represented in this way. Gives a detailed description of the algorithm for determining finite automata. A large number of examples illustrate a capability of the determinization algorithm.https://www.mathmelpub.ru/jour/article/view/67finite state automatadeterminizationweighted directed graph |
| spellingShingle | M. S. Vinogradova S. B. Tkachev I. E. Kandaurova The Determining Finite Automata Process Matematika i Matematičeskoe Modelirovanie finite state automata determinization weighted directed graph |
| title | The Determining Finite Automata Process |
| title_full | The Determining Finite Automata Process |
| title_fullStr | The Determining Finite Automata Process |
| title_full_unstemmed | The Determining Finite Automata Process |
| title_short | The Determining Finite Automata Process |
| title_sort | determining finite automata process |
| topic | finite state automata determinization weighted directed graph |
| url | https://www.mathmelpub.ru/jour/article/view/67 |
| work_keys_str_mv | AT msvinogradova thedeterminingfiniteautomataprocess AT sbtkachev thedeterminingfiniteautomataprocess AT iekandaurova thedeterminingfiniteautomataprocess AT msvinogradova determiningfiniteautomataprocess AT sbtkachev determiningfiniteautomataprocess AT iekandaurova determiningfiniteautomataprocess |