[Solved]: Regular expression for words in a language where each letter appears at least once

Problem Detail: 

What is a regular expression or finite automaton that will accept words in the alphabet $\{a,b,c \}$ where each letter appears at least once?

Acceptable words: $ abc, cba, cbcbcba, abbbcaabb$

Unacceptable words: $aab, babababababa, bbbbbaaaaa$

I would be interested in seeing both the regex and the automaton. Then I can place it into regexper.com

---

In Regular expression to show that all strings contain each symbol atleast once we find the regex

$$ (a+b+c)^*a(a+b+c)^*b(a+b+c)^*c $$

The word $cba$ does not fit, and the answer raises questions about the complexity or size.
For kicks, I draw the automaton [1].

---

COMMENT It's not clear to me at all this is a duplicate to the linked question. They talk in general about deciding if

$$ \qquad \displaystyle L' := \{w \in L: uv = w \text{ for } u \in \Sigma^* \setminus L \text{ and } v \in \Sigma^+ \} $$

is a regular language. None of the answers address my specific case in question. Looking at notes, my guess the alphabet is $\Sigma = \{ a,b,c\}$ and $\Sigma^\ast$ is the free monoid. It's unclear to me what choice of $L$ returns the $L'$ I am looking for.

Or if anyone can show me how this is an intersection, complement or other regular language operation please let me know.

Asked By : john mangual

Answered By : babou

A DFA for your language is:

The name of the states are self descriptive.

Following comments from D.W., here is a way to compute such an automaton. It is a bit tedious and error prone by hand, but easy to do by computer with the proper algorithms. These ideas are to be found in this reference question.

You define 3 languages on the alphabet $\Sigma^*=\{a,b,c\}$, $L_a$, $L_b$, and $L_c$, such that each contains all string that have at least one occurrence of the subscript symbol.

For example $L_a=\{w\mid |w|_a\geq 1\}$

The language you want is $L_a\cap L_b \cap L_c$.

The corresponding finite automata are much easier to define. Then you only have to apply twice the standard crossproduct construction to get the automaton for the intersection.

The advantage of using standard construction is that it spares you the need to prove your result correct (if done by a computer ... I would not trust a human being).

A regular expression is:

$$\begin{align} (\;\;\; (aa^*b & +bb^*a)(a+b)^*c \\ +(bb^*c & +cc^*b)(b+c)^*a \\ +(cc^*a & +aa^*c)(c+a)^*b\;\;\;) \;\; (a+b+c)^* \end{align}$$

You can more or less read it from the DFA. Otherwise, just use the standard algorithms, and good luck.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/45184

3.2K people like this

 Download Related Notes/Documents