Translate from logical formula to regular expression

Question

I want to translate this formula in a regular expression:

Explanation:

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?

Answer 1

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^*$.

Answer 2

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:

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

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?