# Generating regular expressions not containing abc

Let sigma = {a,b,c}. How do I generate a language L that does not containg abc? Any guidance is appreciated!

• Should $L$ contain all words except abc? I.e., are you looking for a regular expression for $L = \Sigma^* \setminus \{ abc \}$? Mar 18, 2020 at 22:45
• Yes! So my L for now contains all words where aaa appears exactly once. But it also generates abc. And I need the L without abc. Mar 18, 2020 at 22:47
• I added an answer that shows how to obtain a regular expression for $L$. Anyway, the language associated to your regular expression does contain the word "abc"... Mar 18, 2020 at 22:53
• all words except $abc$, or all words that do not contain $abc$ [as a subword] ?? Mar 19, 2020 at 1:30
• The latter. Sorry! Mar 19, 2020 at 1:33

Design a DFA that recognizes "abc" (make sure to include all transitions). Complement it (make accepting states non-accepting, and make non-accepting states accepting) in order to get a DFA for $$L = \Sigma^* \setminus \{ abc \}$$. Finally, write down the regular expression of the complemented DFA.

As a brute force solution that does not use DFAs: write a regular expression for all words of lengths 0, 1, 2, and more than 3. This should be easy. Then write, a regular expression for all words of length 3 except abc. For example: $$(b+c)(a+b+c)^2 + ab(a+b) + a(a+c)(a+b+c)$$

Take the union of all the above REs.

• Thank you. But it is only the beginning of the course and we haven't learned, therefore, I am not familiar with DFA :| Mar 18, 2020 at 22:52
• I edited my answer to add an alternative solution. Mar 18, 2020 at 23:04

The language of all words not containing $$abc$$ as a subword can be handled by focussing on the letter $$b$$. Whenever it occurs in the string we should check that one of the following conditions hold:

• it is the first letter of the string
• it is directly after another $$b$$ or after a $$c$$, or symmetrically
• it is directly before ...
• it is the last letter of the string

If that is true, I think it can be handled efficiently with a regular expression.

Be safe, all!