Ambiguity in Graphs and Expressions
- 1 February 1971
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-20 (2) , 149-153
- https://doi.org/10.1109/t-c.1971.223204
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.Keywords
This publication has 9 references indexed in Scilit:
- On Concatenative Decompositions of Regular EventsIEEE Transactions on Computers, 1968
- On Information Lossless Automata of Finite OrderIEEE Transactions on Electronic Computers, 1965
- A New Normal-Form Theorem for Context-Free Phrase Structure GrammarsJournal of the ACM, 1965
- Signal Flow Graph Techniques for Sequential Circuit State DiagramsIEEE Transactions on Electronic Computers, 1963
- THE ABSTRACT THEORY OF AUTOMATARussian Mathematical Surveys, 1961
- Design of Sequential Machines from Their Regular ExpressionsJournal of the ACM, 1961
- Regular Expressions and State Graphs for AutomataIEEE Transactions on Electronic Computers, 1960
- Feedback Theory-Further Properties of Signal Flow GraphsProceedings of the IRE, 1956
- Feedback Theory-Some Properties of Signal Flow GraphsProceedings of the IRE, 1953