1
$\begingroup$

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

enter image description here

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.

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ possible duplicate of How to prove a language is regular? $\endgroup$
    – D.W. ♦
    Aug 12, 2015 at 0:52
  • $\begingroup$ @D.W. He is really asking for the regex and the automaton. He does not seem to question regularity. $\endgroup$
    – babou
    Aug 12, 2015 at 2:39
  • 1
    $\begingroup$ @babou, yes, and that question describes how to find an automaton, from which one can obtain the regexp. Remember, one way that X can be a duplicate of Y if the answers to Y also yield the answer to X -- so you have to look at more than just the title of the question. $\endgroup$
    – D.W. ♦
    Aug 12, 2015 at 2:40
  • $\begingroup$ @D.W. I am not so sure these answers really help here. I may have missed a point. It is kind of messy if one does not see the structure. $\endgroup$
    – babou
    Aug 12, 2015 at 2:46
  • 1
    $\begingroup$ @babou, following those methods immediately leads to an answer. Those methods describe how to find an automaton (e.g., using closure properties -- intersection of the languages "must contain an a", "must contain a b", etc.), and there are standard methods to derive a regexp from an automaton. If the asker has tried using those methods and got stuck at a particular point, they should describe what they tried. What specifically is your point of uncertainty? I don't see anything uncertain, personally. $\endgroup$
    – D.W. ♦
    Aug 12, 2015 at 2:48

1 Answer 1

Reset to default
6
$\begingroup$

A DFA for your language is: enter image description here

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @johnmangual Whatever information or knowledge you already have on your problem should be (as much as reasonable) included in the question so as to focus it on what is relevant. You can see that from the comments on your question. Badly focussed questions lead to negative reactions. --- The cube, as you call it, with its corner ribbons, is the minimal DFA. The regex has star hight 1, which is to be expected given the simple loops on the automaton. BTW, thanks for adding the motivation. $\endgroup$
    – babou
    Aug 12, 2015 at 10:27

Your Answer

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

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