I am creating a program which searches for particular types of strings. The alphabet of these strings are in $\{a, b, c\}$, for which every sub string of length 3 contains exactly $c$. Some strings that follow these constraints are:

$cabcbbca$, $cbb$ and $acaacb$

And strings that don't follow the constraints are:

$aaac$, $ccc$ and $cbcaac$

From this, I can see that a regular expression might need to be made to search for strings that follow the constraints.

I have tried hard coding some regular expressions such as:

$((a \cup b)(a \cup b)c)^*$, which would cover strings like $abcabcabc$, but will obviously not work for all strings, as their are many combinations the strings could be in.

I'm not sure how I could create a general regular expression that could strictly follow any sub string of length 3 to contain exactly one $c$. Any help would be appreciated.

  • $\begingroup$ You're very close - your current regular expression works fine for the middle of the string, but imposes extra restrictions end the ends - it forces non-empty strings to start with 2 non-$c$ letters and end with a $c$. How can you modify it to remove these restrictions? $\endgroup$ Oct 14 '17 at 18:07
  • 3
    $\begingroup$ You could start with a finite automaton (NFA for example) and convert it into the corresponding regexp. $\endgroup$
    – fade2black
    Oct 14 '17 at 18:20
  • $\begingroup$ Do you mean that every sub string of length 3 should have exactly one c? Your example of aaac not being part of the language seems to indicate this. And are strings of length less than 3 allowed? $\endgroup$
    – AcId
    Oct 15 '17 at 9:02
  • $\begingroup$ @AcId Strings less than length 3 are by default apart of the language. Only substrings of length 3 or more need to be considered, so sub strings like cc are valid.accc would fail because of ccc, which is a sub string of length 3 that contains more than one c. All sub strings of length 3 can only contain one c. $\endgroup$
    – RoadRunner
    Oct 15 '17 at 9:20
  • $\begingroup$ @RoadRunner But are all sub strings of length three required to have one c, i.e. are strings such as abab and abbb allowed? $\endgroup$
    – AcId
    Oct 15 '17 at 9:23

The following regular language should match your specification. I've used a slightly different notation than yours, denoting $(a \cup b)$ as $\{a,b\}$.

$\mathcal{L} = c \cup c \{a,b\} \cup c \{a,b\} \{a,b\} \cup \{a,b\} \cup \{a,b\}\{a,b\} \cup \left( ((\{a,b\}c) \cup c)? (\{a,b\}\{a,b\}c)*\right)$

$?$ denotes repetition zero or one time, and $*$ repetition zero or more times.

It can be written in a more compact representation as: $\mathcal{L} = c\{a,b\}\{a,b\} \cup \{a,b\}?c?\{a,b\}? \cup (\{a,b\}?\{a,b\}?c)?(\{a,b\}\{a,b\}c)* $

  • $\begingroup$ Updated answer to also include the strings $c \{a,b\}$ and $c\{a,b\}\{a,b\}$. $\endgroup$
    – AcId
    Oct 15 '17 at 10:05
  • $\begingroup$ @Evil Have removed "Edit" from the answer. $\endgroup$
    – AcId
    Oct 15 '17 at 10:27
  • $\begingroup$ I hope you are aware that "?" is not standard operator here. $\endgroup$
    – Evil
    Oct 15 '17 at 10:32
  • $\begingroup$ I am aware that most textbooks only include the union, concatenation and Kleene star operations. However, the ? operator can easily be derived from these operators, i.e.$ A? = A \cup \epsilon$. Further, it was explicitly stated in the question that it was for use in a program (which I interpret as a computer program), and I think most programming languages that incorporate regular expressions have the ? operator. $\endgroup$
    – AcId
    Oct 15 '17 at 10:50
  • $\begingroup$ Thanks for the answer. This supplements my NFA really well. $\endgroup$
    – RoadRunner
    Oct 15 '17 at 12:11

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.