10
votes
Accepted
Is the language given by the regex (ab)* star-free?
No. $L=(ab)^*$ is star-free. A word is in $L$ iff
It starts with $a$ (or is empty)
It ends with $b$ (or is empty)
It does not contain any consecutive $a$'s
It does not contain any consecutive $b$'s
...
D.W.♦
- 154k
2
votes
Why can't I prove that the regular language is closed under concatenation by this way?
Actually, that works if you add $\varepsilon$-transitions between final states of $M_1$ and the initial state of $M_2$.
His argument of "maybe the cut of $w$ was wrong and you should have waited ...
- 12.3k
Only top scored, non community-wiki answers of a minimum length are eligible