I want to translate this formula in a regular expression:

Logical formula


The alphabet is : $\{a, b, c\}$

$w(p) = a$ , means on the position $p$ in the word stands an $a$.

For the regular expression I can only use the following operations:

concatenation, union and star (no difference)

and I can use the empty set.

Generally, the formula defines a language which does not allow words where an "$a$" follows a "$c$".

In the language: $\{"","a","b","c","ba","ab",\dots\}$

Not in the language: $\{"ac","baca",\dots\}$

How can a regular expression looks like?


2 Answers 2


Your logical formula means that the patterns of the form $a(a+c)^*c$ are forbidden in the words of your language, since if you have an $a$ in position $p$ and a $c$ in position $q > p$, then you should have a $b$ somewhere between $a$ and $c$. Now, if you think about it, forbidding patterns of the form $a(a+c)^*c$ is just the same thing as forbidding the pattern $ac$, since any word of $a(a+c)^*c$ contains a factor of the form $ac$. It follows that your language is the complement of the language $A^*acA^*$ (where $A$ is the alphabet $\{a, b, c\}$).

Now you can compute the minimal DFA of the complement of the language $A^*acA^*$ and derive from it the regular expression $(b + c + a(a^*b))^*a^*$.


Such a string can clearly begin with any number of $b$’s and $c$’s in any order: $(b+c)^*$. That could be the end of it, or that could be followed by one or more $a$’s; now we’re up to $(b+c)^*+(b+c)^*aa^*$ (which could of course also be written $(b+c)^*(\lambda+aa^*)$). If there’s more after that, it must begin with a $b$, which brings it to this:


And at that point you’re essentially starting over: you can begin again with any number of $b$’s and $c$’s in any order. Can you make the final modification to get a regular expression that does all of this?

  • $\begingroup$ So in the final step I have to eliminate the possibility for the occurrence of an a follows a c in your current expression and short it, like @J.-E. Pin did. $\endgroup$
    – Georges
    Oct 30, 2013 at 17:21
  • $\begingroup$ @Georges: Actually, the final step is much easier than that: just take the star of the displayed expression. Yes, you could also simplify it a bit, but that’s not essential. $\endgroup$ Oct 30, 2013 at 18:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .