# Can words in regular languages be generated by automata in a unique way?

If $L\subset \Sigma^\ast$ is a regular language then it is known that we can find a directed graph (aka automaton) $G$ with edges labelled with symbols from $\Sigma$, an ‘initial’ vertex, and a set of ‘terminal’ vertices, with the property that a word $w$ is in $L$ iff $w$ is the sequence of edge labels along a path from the initial vertex to a terminal vertex.

It’s possible that the same word can appear as a result of different paths in $G$. Can we guarantee that for any regular $L$ we can find a $G$ such that each word in $L$ appears as a path in $G$ in a unique way?

(I’m interested in this because I want to know whether the solution to the problem I worked on here applies cleanly to any regular language, or just for a certain class of them.)

• This question doesn't look like a research-level question in TCS. It should perhaps be moved to cs.stackexchange.com Aug 29 '13 at 10:23

Maybe I misunderstood your question, but wouldn't a Deterministic Finite Automaton do what you want?

• You may be right. I'm not knowledgeable in this area and I've been thinking in terms of generation of strings, not recognition. But now I think about it, you're probably right. I'll mull over it for a little bit. Aug 23 '10 at 21:47
• Yes, it's straightforward. I just came at this at the wrong angle. Thanks. Aug 23 '10 at 21:51

You may want to know that there's also a notion of ambiguity for regular expressions. Also, you can decide ambiguity for NFAs in $O(n^2)$.

2. There exists a different type of automaton called Unambiguous Finite Automaton ($UFA$), which is a non deterministic finite automaton which has at most one accepting path for each word.