Ambiguity in Graphs and Expressions
Ambiguity in Graphs and Expressions
复制标题
图形和表达式的歧义
DOI：
--
复制
发表时间：
1971
影响因子：
3.7
通讯作者：
G. Ott
中科院分区：
文献类型：
--
作者：
R. V. Book;S. Even;S. Greibach;G. Ott
如果事件中的每个磁带只能以一种方式从正则表达式生成，则该正则表达式称为明确的。用于构造表达式的流图技术被证明保持图的歧义，因此，如果图是确定性自动机的图，则该表达式是明确的。描述了一种用于生成保持给定正则表达式的多义性的非确定自动机的过程。最后，给出了一个检验给定表达式是否有歧义的步骤。
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.