
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 flowgraphtechnique 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