2
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • $\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$
    – cardobard_box
    Oct 14, 2017 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, 2017 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, 2017 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, 2017 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, 2017 at 9:23

1 Answer 1

Reset to default
2
$\begingroup$

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)* $

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.