1
$\begingroup$

L ⊆ ∑* is a regular language. Show that L^+ (aka kleene plus) is a regular language by describing how you can build a DFA or NFA for the language.

I would build a NFA. That NFA must have exactly one starting state and one end state, where the starting state is never the end state.

The amount of characters of the given language equals the amount of states of the NFA +1.

Every state except for the end state has an (outgoing) arrow to the next state where every single character of the language occurs exactly once (ordered aka one after the other).

If the language is made up of just one character, do: The end state has an outgoing arrow to itself with that one character of the language.

Else do: The end state has an outgoing arrow to the second state (I mean that state where the starting state points at) with the first character of the language.

Here is an example:

Given is language (aba)^+ where ^+ means exponent +

The NFA for this language would look like this ("Beispiel" means example):

enter image description here

Do you agree with my idea and do you have any improvements?

For the case the language is made up of several pairs, for example (aba, ab, bb)^+ I would just do the entire procedure for every single. In the end you will have a NFA for language (aba)^+ another NFA for (ab)^+ and NFA for (bb)^+. Then concatenate all NFA to one entire NFA.

|cite|improve this question
$\endgroup$
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – D.W.♦ Nov 7 '17 at 23:26
2
$\begingroup$

You can use Thompson's construction. It constructs NFA with $\epsilon$ moves. But remove the forward $\epsilon$-transition from the new start state into the new final state since you are interested in $L^+$ and not in $L^*$.

NFA with $\epsilon$ moves is a generalization of NFA and DFA. But you can systematically transform any NFA with $\epsilon$ moves into equivalent NFA without $\epsilon$ moves and DFA. Look here for more.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ In that link you provided, what exactly is meant by N(s)? If I understood correctly, it is a NFA for the language without +. As example, if we have language (ab)^+, N(s) is the NFA for the language ab? $\endgroup$ – cnmesr Nov 7 '17 at 23:02
  • 1
    $\begingroup$ It writes "N(s) and N(t) is the NFA of the subexpression s and t, respectively". In your case you can substitute $N(s)$ with the DFA or NFA for $L$. Since you are given that $L$ is a regular set, there is DFA/NFA accepting $L$. Then apply Thompson's construction. $\endgroup$ – fade2black Nov 7 '17 at 23:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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