<p>You may want to know that there's also a notion of <a href="http://scholar.google.com/scholar?cluster=6789779090132465473" rel="nofollow">ambiguity for regular expressions</a>. Also, you can <a href="http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4038507" rel="nofollow">decide ambiguity for NFAs</a> in $O(n^2)$.</p>

CC BY-SA 2.5
2010-09-07T16:55:22.247Z
2010-09-08T08:23:39.607Z
2010-09-08T08:23:39.607Z
Radu GRIGore
<p>A DFA, as stated, can answer your question.</p>

<p>If you are interested in a small automaton for this task there are three things which comes to mind:</p>

<ol>
<li>DFA can be optimized, so you could find the minimal (state-wise) automaton for the langauge.</li>
<li>There exists a different type of automaton called <em>Unambiguous Finite Automaton</em> ($UFA$), which is a non deterministic finite automaton which has at most one accepting path for each word.</li>
<li>Unlike DFA, UFA optimization is NP-hard hence the minimal automaton for your task is unlikely to be found efficiently for a general language.</li>
</ol>

CC BY-SA 3.0
2014-01-08T09:21:57.570Z
2014-01-08T09:21:57.570Z
R B
<p>Maybe I misunderstood your question, but wouldn't a Deterministic Finite Automaton do what you want?</p>

CC BY-SA 2.5
2010-08-23T21:47:08.840Z
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.
Dan Piponi
CC BY-SA 2.5
2010-08-23T21:51:59.333Z
Yes, it's straightforward. I just came at this at the wrong angle. Thanks.
Dan Piponi
CC BY-SA 2.5
2010-08-23T21:41:02.180Z
2010-08-23T21:41:02.180Z
Aryabhata
<p>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.</p>

<p>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 <em>unique</em> way?</p>

<p>(I’m interested in this because I want to know whether the solution to the problem I worked on <a href="http://blog.sigfpe.com/2010/08/constraining-types-with-regular.html">here</a> applies cleanly to any regular language, or just for a certain class of them.)</p>

CC BY-SA 3.0
2013-08-29T10:23:18.903Z
This question doesn't look like a research-level question in TCS. It should perhaps be moved to http://cs.stackexchange.com/
J.-E. Pin
<automata-theory><fl.formal-languages>
Can words in regular languages be generated by automata in a unique way?
Dan Piponi
# Can words in regular languages be generated by automata in a unique way?

(Asked by: username_0 on 2010-08-23)

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](http://blog.sigfpe.com/2010/08/constraining-types-with-regular.html) applies cleanly to any regular language, or just for a certain class of them.)

**Tags:** automata-theory, fl.formal-languages
> **Comments:**
> **username_1**: This question doesn't look like a research-level question in TCS. It should perhaps be moved to http://cs.stackexchange.com/  

---

## 3 answers

### Answer by username_4 on 2010-08-23. Score: 14 | Accepted answer

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

> **Comments:**
> **username_0**: 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.  
> **username_0**: Yes, it's straightforward. I just came at this at the wrong angle. Thanks.  

---

### Answer by username_2 on 2010-09-07. Score: 5

You may want to know that there's also a notion of [ambiguity for regular expressions](http://scholar.google.com/scholar?cluster=6789779090132465473). Also, you can [decide ambiguity for NFAs](http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4038507) in $O(n^2)$.


---

### Answer by username_3 on 2014-01-08. Score: 1

A DFA, as stated, can answer your question.

If you are interested in a small automaton for this task there are three things which comes to mind:

1. DFA can be optimized, so you could find the minimal (state-wise) automaton for the langauge.
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.
3. Unlike DFA, UFA optimization is NP-hard hence the minimal automaton for your task is unlikely to be found efficiently for a general language.


---

