# Creating regular expression with sub sequences of strings

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.

• 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? Oct 14 '17 at 18:07
• You could start with a finite automaton (NFA for example) and convert it into the corresponding regexp. Oct 14 '17 at 18:20
• 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?
– AcId
Oct 15 '17 at 9:02
• @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. Oct 15 '17 at 9:20
• @RoadRunner But are all sub strings of length three required to have one c, i.e. are strings such as abab and abbb allowed?
– 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)*$

• Updated answer to also include the strings $c \{a,b\}$ and $c\{a,b\}\{a,b\}$.
– AcId
Oct 15 '17 at 10:05
• @Evil Have removed "Edit" from the answer.
– AcId
Oct 15 '17 at 10:27
• I hope you are aware that "?" is not standard operator here.
– Evil
Oct 15 '17 at 10:32
• 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.
– AcId
Oct 15 '17 at 10:50
• Thanks for the answer. This supplements my NFA really well. Oct 15 '17 at 12:11