Reference. Self-certifying Railroad Diagrams: Or: How to Teach Nondeterministic Finite Automata

Ralf Hinze · MPC · 2019 · parsing · DOI

Cite
Cite as @hinze-2019-self (helia, typst) · \cite{hinze-2019-self} (LaTeX)
BibTeX
bibtex · 1 line
@inbook{hinze-2019-self, title={Self-certifying Railroad Diagrams: Or: How to Teach Nondeterministic Finite Automata}, ISBN={9783030336363}, ISSN={1611-3349}, url={http://dx.doi.org/10.1007/978-3-030-33636-3_5}, DOI={10.1007/978-3-030-33636-3_5}, booktitle={Mathematics of Program Construction}, publisher={Springer International Publishing}, author={Hinze, Ralf}, year={2019}, pages={103–137} }
hayagriva YAML (typst)
yaml · 15 lines
hinze-2019-self:
  type: chapter
  title: 'Self-certifying Railroad Diagrams: Or: How to Teach Nondeterministic Finite Automata'
  author: Hinze, Ralf
  date: 2019
  page-range: 103-137
  url: http://dx.doi.org/10.1007/978-3-030-33636-3_5
  serial-number:
    doi: 10.1007/978-3-030-33636-3_5
    isbn: '9783030336363'
    issn: 1611-3349
  parent:
    type: book
    title: Mathematics of Program Construction
    publisher: Springer International Publishing
Download: hinze-2019-self.bib · hinze-2019-self.yml
Cites 16 works (3 here)
With notes (3)

Programming Techniques: Regular expression search algorithm thompsonProgrammingTechniquesRegular1968CACM · 1968
A method for locating specific character strings embedded in character text is described and an implementation of this method in the form of a compiler is discussed. The compiler accepts a regular expression as source language and produces an IBM 7094 program as object language. The object program then accepts the text to be searched as input and produces a signal every time an embedded string in the text matches the given regular expression. Examples, problems, and solutions are also presented.
DOI

Derivatives of Regular Expressions brzozowskiDerivativesRegularExpressions1964JACM · 1964
Kleene’s regular expressions, which can be used for describing sequential circuits, were defined using three operators (union, concatenation and iterate) on sets of sequences. Word descriptions of problems can be more easily put in the regular expression language if the language is enriched by the inclusion of other logical operations. However, in the problem of converting the regular expression description to a state diagram, the existing methods either cannot handle expressions with additional operators, or are made quite complicated by the presence of such operators.In this paper the notion of a derivative of a regular expression is introduced and the properties of derivatives are discussed. This leads, in a very natural way, to the construction of a state diagram from a regular expression containing any number of logical operators.
DOI

Finite Automata and Their Decision Problems rabinFiniteAutomataTheir1959IBM Journal of Research and Development · 1959
Finite automata are considered in this paper as instruments for classifying finite tapes. Each onetape automaton defines a set of tapes, a two-tape automaton defines a set of pairs of tapes, et cetera. The structure of the defined sets is studied. Various generalizations of the notion of an automaton are introduced and their relation to the classical automata is determined. Some decision problems concerning automata are shown to be solvable by effective algorithms; others turn out to be unsolvable by algorithms.
DOI
External (13)
hinze-2019-self reference entries/refs/hinze-2019-self/hinze-2019-self.hel