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

$\endgroup$
  • $\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 '13 at 10:23
14
$\begingroup$

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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