0
$\begingroup$

Supposing we have either a NFA or a DFA with accepted language $L$, what is $L^*$? And how can I build an automaton that accepts it?

$\endgroup$
0
$\begingroup$

$L^*$ is the Kleene closure of $L$. This is the language of all strings that can be made by taking a finite number of (not necessarily different) strings from $L$ and concatenating them. More formally,

$$L^* = \{\varepsilon\}\cup\{w\in\Sigma^*\mid \exists k\geq 1\,\exists w_1, \dots, w_k\in L \text{ such that } w = w_1\cdot\dots\cdot w_k\}\,.$$

Or, if you prefer, for $k\geq 1$, let $$L^k = \{w_1\cdot \dots \cdot w_k\mid w_1, \dots, w_k\in L\}$$ and then $L^* = \{\varepsilon\}\cup L^1 \cup L^2 \cup L^3 \cup\cdots\,$.

As for how to produce an automaton that accepts that, I suggest you think about it some more yourself, now that you know what it is you're trying to do. A hint would be to use nondeterminism to "guess" where the words $w_2, \dots, w_k$ begin.

$\endgroup$
  • $\begingroup$ Thank you very much for your reply! What about adding a sink state to which all the final states are connected through a epsilon transition and then connect this sink to the initial state? In this way I should be able to concatenate all the accepted strings. Further, I could add a final state connected to the initial state through a epsilon transition in order to be able to accept epsilon. $\endgroup$ – lelli Feb 17 '18 at 10:07
  • $\begingroup$ @lelli That looks like it should work. Check all the details to make sure you've not missed anything. (I don't think you have but you should still check.) $\endgroup$ – David Richerby Feb 17 '18 at 11:09

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.