Regular Expressions Help

Question

I need a little help with Regular Expressions.

The allowed operations are obviously + (union) , * (Kleene star) and concatenation.

I have to write Regex for the following 2 examples. I have tried a lot, but havn't succeed:

1. Write a Regex that receives all the words above $\Sigma = \{s,t\}$ which include at least two instances of the letter t, and don't include the subword stt.

2. Write a Regex that receives all the words above $\Sigma = \{s,t\}$ which include the subword stts, and don't include the subword tss.

I thought about these 2 alot. I understood that in 1 I have to somehow make sure that each 2 t's are seperated by s (except some exceptions). the same trick should be implemented in 2 too.

Thanks ;)

Answer 1

For 1, one must be carefiul to include variants starting with at least two $t$: ttt*(s+st)* Then there are the variants starting with one $t$: tss*t(s+st)* And those starting with no $t$: ss*tss*t(s+st)*. These can be nicely combined into (tt*+s*tss*)t(s+st)*, a pattern one might not have guessed out of the blue.

Answer 2

I'll use $|$ for alternation (I think this is more standard than $+$).

---

For your first example, if you have a tt in your expression, you won't be able to have any s before it. I think this works:

$$(t)^*t(s)^*t(st\,|\,s)^*$$

---

In the second problem, you need an stts, and the strings on the right cannot start with an s and cannot have two consecutive s's. The strings on the left can either be completely s or not have consecutive s's. I think this covers all of the possibilities:

$$\left((t\,|\,st)^*\,|\,(s)^*\right)stts(t\,|\,ts)^*$$