Build a regular expression that specifies the language L in the alphabet Σ = {a, b, c}: L = {w : w does not contain aaab}.

For this task, you also need to build a deterministic finite automaton, but I coped with this without problems.

I know how to build a regular expression so that the word contains the fragment aaab. regular expression:

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

(*) - iteration

But I don't know how to build the regular so that it doesn't contain the aaab fragment.

If you have any thoughts or ideas, I would be grateful if you share them.

(As an example, I can give a regular expression for the language L = {w: there is no fragment abac in the word w}. Alphabet {a,b,c}.regular expression


1 Answer 1


Not having $aaab$ is equivalent to requiring that all (maximal) runs of at least three $a$s are either followed by $c$ or are word-final. As such we control how $a$-runs appear when building the regex: in non-word-final positions we allow $a^*c$ as a block, then add the special cases $ab$ and $aab$ alongside the character-blocks $b$ and $c$. The word-final run of $a$ can be handled easily, and we get the final result of $$((a^*c)+ab+aab+b+c)^*a^*$$


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.