Metraipolis › archive › dc_bf96757b26bb

Glushkov's construction algorithm — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Glushkov%27s_construction_algorithm
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-15T19:30:21.506Z
SHA-256 of the archived text
3a55aadbbfd35ea5309c78c159d955d8565b801369137d8e2c91b4c89cee3d8e
Stable URL of this page
https://metraipolis.com/documento/dc_bf96757b26bb

How to cite

Glushkov's construction algorithm — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Glushkov%27s_construction_algorithm (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_bf96757b26bb (Metraipolis archive dc_bf96757b26bb, sha256 3a55aadbbfd35ea5309c78c159d955d8565b801369137d8e2c91b4c89cee3d8e)
BibTeX
@misc{dcbf96757b26bb,
  title = {Glushkov's construction algorithm — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Glushkov%27s_construction_algorithm},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_bf96757b26bb; sha256 3a55aadbbfd35ea5309c78c159d955d8565b801369137d8e2c91b4c89cee3d8e},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Glushkov%27s_construction_algorithm. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In computer science theory – particularly formal language theory – Glushkov's construction algorithm, invented by Victor Mikhailovich Glushkov, transforms a given regular expression into an equivalent nondeterministic finite automaton (NFA). Thus, it forms a bridge between regular expressions and nondeterministic finite automata: two abstract representations of the same class of formal languages. A regular expression may be used to conveniently describe an advanced search pattern in a "find and replace"–like operation of a text processing utility. Glushkov's algorithm can be used to transform it into an NFA, which furthermore is small by nature, as the number of its states equals the number of symbols of the regular expression, plus one. Subsequently, the NFA can be made deterministic by the powerset construction and then be minimized to get an optimal automaton corresponding to the given regular expression. The latter format is best suited for execution on a computer. From another, more theoretical point of view, Glushkov's algorithm is a part of the proof that NFA and regular expressions both accept exactly the same languages; that is, the regular languages. The converse of Glushkov's algorithm is Kleene's algorithm, which transforms a finite automaton into a regular expression. The automaton obtained by Glushkov's construction is the same as the one obtained by Thompson's construction algorithm, once its ε-transitions are removed. Glushkov's construction algorithm is also called The algorithm of Berry-Sethi, named after Gérard Berry and Ravi Sethi who worked on this construction.

Tema degli esploratori: statistica e scienza dei dati (deposito sistematico; ricerca «algorithm»).
Fonte: Wikipedia in inglese, voce «Glushkov's construction algorithm» — https://en.wikipedia.org/wiki/Glushkov%27s_construction_algorithm
Wikidata Q827139 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q827139
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Glushkov%27s_construction_algorithm?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1353379790, consultata il 2026-10-15T18:37:30.200Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 9483e06b801782b2ac19ebe5b731e25ddbe149b123962fc42e8a324775ea35ad