6
$\begingroup$

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.)

Improve this question
$\endgroup$
1
  • $\begingroup$ This question doesn't look like a research-level question in TCS. It should perhaps be moved to cs.stackexchange.com $\endgroup$
    – J.-E. Pin
    Aug 29, 2013 at 10:23

3 Answers 3

Reset to default
14
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – user381
    Aug 23, 2010 at 21:47
  • $\begingroup$ Yes, it's straightforward. I just came at this at the wrong angle. Thanks. $\endgroup$
    – user381
    Aug 23, 2010 at 21:51
5
$\begingroup$

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)$.

Improve this answer
$\endgroup$
1
$\begingroup$

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.
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.