Accession Number : AD0709711

Title :   AMBIGUITY IN GRAPHS AND EXPRESSIONS,

Corporate Author : HARVARD UNIV CAMBRIDGE MASS DIV OF ENGINEERING AND APPLIED PHYSICS

Personal Author(s) : Book,Ronald ; Even,Shimon ; Greibach,Sheila ; Ott,Gene

Report Date : MAY 1970

Pagination or Media Count : 25

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)

Descriptors :   (*DIGITAL COMPUTERS, THEORY), (*GRAPHICS, AUTOMATA), ARTIFICIAL INTELLIGENCE, LEARNING MACHINES, ALGORITHMS, THEOREMS

Subject Categories : Computer Hardware
      Bionics

Distribution Statement : APPROVED FOR PUBLIC RELEASE