0
$\begingroup$

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

Improve this question
$\endgroup$
6
  • $\begingroup$ Should $L$ contain all words except abc? I.e., are you looking for a regular expression for $L = \Sigma^* \setminus \{ abc \}$? $\endgroup$
    – Steven
    Mar 18, 2020 at 22:45
  • $\begingroup$ 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. $\endgroup$
    – TanaM
    Mar 18, 2020 at 22:47
  • $\begingroup$ 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"... $\endgroup$
    – Steven
    Mar 18, 2020 at 22:53
  • 2
    $\begingroup$ all words except $abc$, or all words that do not contain $abc$ [as a subword] ?? $\endgroup$
    – Hendrik Jan
    Mar 19, 2020 at 1:30
  • $\begingroup$ The latter. Sorry! $\endgroup$
    – TanaM
    Mar 19, 2020 at 1:33

2 Answers 2

Reset to default
1
$\begingroup$

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.

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

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!

Improve this answer
$\endgroup$

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.