New answers tagged

0 votes

Why can't I prove that the regular language is closed under concatenation by this way?

I would assume you are familiar with regular expressions since that was discussed in the video you linked. However, it seems like nondeterminism hasn't been introduced. Consider two regular ...
Russel's user avatar
  • 2,590
3 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 ...
Nathaniel's user avatar
  • 12.3k
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.'s user avatar
  • 154k

Top 50 recent answers are included