CIS 2620 Notes 3.2

Kleene* Operation#

Let us define the Kleene $*$ operation:

$$A* = \{w | w\text{ can be split into multiple parts such that each part is in } A \}$$

$A*$ is another way for saying repeated concatenation. $A*$ is the set of strings that are some concatenation of strings of $A$: $$A* = \{\mathcal{E}, A, A.A, A.A.A, etc\}$$

The empty string $\mathcal{E}$ is always in $A*$.

Example: Let $A = \{w | \text{ w contains exactly 2 a’s}\}$.
In this case, $A* = \{w | w \text{ is empty or contains a strictly positive even number of a’s}\}$

Theorem: The class of regular languages is closed under Kleene$*$

Proof: Consider a regular language A, and let $M$ be a DFA accepting it. We will prove by constructing an NFA that accepts $A*$.

Given an input $w$, $M’$ needs to check if we can split $w$ into parts such that each part is accepted by $M$. To do this, let us begin executing $M$ on $w$. When the current state is an accepting state, we decide nondeterministically to switch to the initial state and restart $M$ on the rest of the string using an $\mathcal{E}$ transition. If we end the string at an accepting state at some thread, that means that either the entire string was valid under $M$, or it was split into parts that were valid under $M$. The construction looks something like this:

However, we have an issue. This construction might reject $\mathcal{E}$, which is always in $A*$. However, this is an easy solution. All we need to do is begin with an accepting state that has an $\mathcal{E}$ transition to the initial state of $M$. This way, if we have an empty string, it will automatically be valid, since it starts at an accepting state. However, if there are characters left in the string, it is forced to move forward, since there are no other threads for characters left at that state.