Assume L is regular language, define 𝐿1 = {𝑣𝑤: 𝑣 ∈ 𝐿,𝑤 ∉ 𝐿}, prove or dispute L1 regular or not ?

  • 1
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving homework-style exercises for you is unlikely to really do that. Try to think about why you can't solve this exercise yourself and ask a question about that. $\endgroup$ – David Richerby Apr 14 '18 at 8:04

It’s regular.

First we can gain a DFA $M$ which accepts the given language $L$. Similarly we have a DFA $\bar M$ which accepts regular language $\bar L$.

Then we can construct a new NFA by adding an $\epsilon$ transition from all the final states in $M$ to $\bar M$’s initial state, which accepts that required language.

  • $\begingroup$ ye when i got 2 different languages its the way to solve it, building 2 separeted DFAs... but can u draw it with steps ? what is the right syntax to prove such question ? $\endgroup$ – user87202 Apr 14 '18 at 15:36
  • $\begingroup$ I'm not sure if I understand your question. It's basically to connect the two DFA $M$ and $\bar M$ with $\epsilon$ transition. $\endgroup$ – Wen Apr 14 '18 at 19:24

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