AMBIGUITY IN GRAPHS AND EXPRESSIONS,
Abstract
A regular expression is called unambiguous if every tape in the event can be generated from the expression in one way only. The flow-graph-technique for constructing an expression is shown to preserve ambiguities of the graph, and thus, if the graph is that of a deterministic automaton, the expression is unambiguous. A procedure for generating a nondeterministic automaton which preserves the ambiguities of the given regular expression is described. Finally, a procedure for testing whether a given expression is ambiguous is given. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1970
- Accession Number
- AD0709711
Entities
People
- Gene Ott
- Ronald Book
- Sheila Greibach
- Shimon Even
Organizations
- Harvard University