| dbo:abstract
|
- Beim Berry-Sethi-Verfahren (nach Gérard Berry und ; auch Glushkov-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 , Transitiver Abschluss und Vereinigung ).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 . (de)
- In computer science theory – particularly formal language theory – the Glushkov 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. (en)
- En informatique théorique et notamment en théorie des automates finis, la construction de Glushkov ou algorithme de Glushkov est un procédé pour construire un automate à partir d'une expression rationnelle. Elle est attribuée à l'informaticien soviétique Victor Glushkov. L'automate obtenu est non déterministe, et de même taille (comptée en nombre d'états) que la taille (comptée en nombre de symboles) de l'expression rationnelle.Il a été observé que l'automate de Glushkov est le même que l'automate obtenu en supprimant les ε-transitions de l'automate obtenu par la méthode de Thompson. La construction de Glushkov est aussi appelée algorithme de Berry-Sethi, d'après Gérard Berry et Ravi Sethi qui ont travaillé sur cette construction. (fr)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 10004 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdfs:comment
|
- In computer science theory – particularly formal language theory – the Glushkov 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. (en)
- Beim Berry-Sethi-Verfahren (nach Gérard Berry und ; auch Glushkov-Konstruktion, nach Wiktor Michailowitsch Gluschkow) handelt es sich um einen Algorithmus zur Überführung eines regulären Ausdrucks in einen nichtdeterministischen endlichen Automaten. 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 . (de)
- En informatique théorique et notamment en théorie des automates finis, la construction de Glushkov ou algorithme de Glushkov est un procédé pour construire un automate à partir d'une expression rationnelle. Elle est attribuée à l'informaticien soviétique Victor Glushkov. L'automate obtenu est non déterministe, et de même taille (comptée en nombre d'états) que la taille (comptée en nombre de symboles) de l'expression rationnelle.Il a été observé que l'automate de Glushkov est le même que l'automate obtenu en supprimant les ε-transitions de l'automate obtenu par la méthode de Thompson. (fr)
|
| rdfs:label
|
- Berry-Sethi-Verfahren (de)
- Glushkov's construction algorithm (en)
- Construction de Glushkov (fr)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:knownFor
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is dbp:knownFor
of | |
| is foaf:primaryTopic
of | |
