Metraipolis › archive › dc_dbd6a6174bac

Berry-Sethi-Verfahren — Wikipedia (de)

Source
Wikipedia (de)
Original
https://de.wikipedia.org/wiki/Berry-Sethi-Verfahren
License (as archived)
CC-BY-SA-4.0
Archived
2026-11-01T08:09:54.882Z
SHA-256 of the archived text
8f7f289bf2404bdd46f0b338fda73221e4a7ad70b79c563f3e05e871a3860072
Stable URL of this page
https://metraipolis.com/documento/dc_dbd6a6174bac

How to cite

Berry-Sethi-Verfahren — Wikipedia (de) — Wikipedia (de), https://de.wikipedia.org/wiki/Berry-Sethi-Verfahren (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_dbd6a6174bac (Metraipolis archive dc_dbd6a6174bac, sha256 8f7f289bf2404bdd46f0b338fda73221e4a7ad70b79c563f3e05e871a3860072)
BibTeX
@misc{dcdbd6a6174bac,
  title = {Berry-Sethi-Verfahren — Wikipedia (de)},
  howpublished = {Wikipedia (de)},
  url = {https://de.wikipedia.org/wiki/Berry-Sethi-Verfahren},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_dbd6a6174bac; sha256 8f7f289bf2404bdd46f0b338fda73221e4a7ad70b79c563f3e05e871a3860072},
  year = {2026}
}

Archived text

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

Beim Berry-Sethi-Verfahren (nach Gérard Berry und Ravi Sethi; auch Gluschkow-Konstruktion, nach Wiktor Michailowitsch Gluschkow) handelt es sich um einen Algorithmus zur Überführung eines regulären Ausdrucks in einen nichtdeterministischen endlichen Automaten. Zunächst wird dabei der reguläre Ausdruck in eine Baumstruktur überführt. Die Knoten entsprechen den Regeln des regulären Ausdrucks (Konkatenation ⋅ {\displaystyle \cdot } , Transitiver Abschluss ∗ {\displaystyle ^{*}} und Vereinigung ∣ {\displaystyle \mid } ). Die Blätter repräsentieren die Elemente des Eingabealphabets im regulären Ausdruck, also genau die Zeichen, aus denen sich gültige Wörter zusammensetzen können. Alle weiteren Berechnungen finden mit Hilfe dieser Darstellungsform statt. Stellt man sich nun einen Punkt vor, der beginnend bei der Wurzel des Syntaxbaums um den Baum herumwandert, so können sukzessive alle Wörter des regulären Ausdrucks erzeugt werden. Mit Hilfe dieses Punktes wird nun der endliche Automat konstruiert. Die Zeitkomplexität des Verfahrens ist O ( n 2 ) {\displaystyle {\mathcal {O}}(n^{2})} .

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in tedesco, in ordine alfabetico).
Fonte: Wikipedia in tedesco, voce «Berry-Sethi-Verfahren» — https://de.wikipedia.org/wiki/Berry-Sethi-Verfahren
Wikidata Q827139: «Algorithm relating regular expressions to NFAs» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q827139
Autori: i contributori di Wikipedia (cronologia: https://de.wikipedia.org/wiki/Berry-Sethi-Verfahren?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 257381204, consultata il 2026-11-01T07:59:30.996Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: d7c8c1d94c3bad25bbf68ad8e56d1d59e57b9dee2b04ae1a89939e400871d515