Kleene-stjerne af et regulært sprog

Vi har et regulært sprog L. Vi viser, at Kleene-stjernen af sproget L igen er et regulært sprog.

Hvad er Kleene-stjernen af et sprog

Kleene-stjernen af sproget L betegner vi L^∗. Den indeholder alle de ord, som kan sammensættes ved konkatenering af et endeligt antal ord fra sproget L. Vi kan definere Kleene-stjernen som:

$$L^{\ast }=\{a_1\circ a_2\circ \cdots \circ a_n|a_i\in L,n\in {\mathbb{N}}_0\},$$

hvor ∘ betegner konkatenering. Kleene-stjernen indeholder også det tomme ord, dvs. ϵ.

Formel fremgangsmåde

Vi går frem på samme måde som ved konkatenering af sprog. I stedet for at forbinde to forskellige automater forbinder vi blot én automat — fra automatens accepttilstande fører vi epsilon-overgange til automatens starttilstand. Kleene-stjernen skal dog også indeholde det tomme ord. Hvordan sørger vi for det? Vi kan gøre starttilstanden til en accepttilstand. Så ville en sådan automat acceptere det tomme ord, men den kunne også acceptere nogle andre ord. Derfor opretter vi i stedet en ny starttilstand og fører fra denne nye starttilstand en epsilon-overgang til den oprindelige starttilstand.

Vi har et regulært sprog L₁ og en automat, som accepterer dette sprog:

$$\begin{array}{rcl}{A}_1& =& ⟨Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_0,F_1⟩\end{array}$$

Vi konstruerer en ikke-deterministisk automat A = ⟨Q, Σ, δ, q_s, F⟩, for hvilken der gælder:

• Q = Q₁ ∪ {q_s}
• Σ= Σ₁
• F = F₁ ∪ {q_s}

Overgangsfunktionen δ definerer vi således:

$$\delta (q,a)=\{\begin{array}{lll}{\delta }_1(q,a)& \text{hvis}& q\in Q_1\wedge q\notin F_1\\ {\delta }_1(q,a)& \text{hvis}& q\in F_1\wedge a\ne ϵ\\ {\delta }_1(q,a)\cup \left\{q_0\right\}& \text{hvis}& q\in F_1\wedge a=ϵ\\ \left\{q_0\right\}& \text{hvis}& q=q_s\wedge a=ϵ\\ \mathrm{\varnothing }& \text{hvis}& q=q_s\wedge a\ne ϵ\end{array}$$

Eksempel

Vi ser på denne automat A₁, som accepterer ordene 00 eller 11:

Kleene-stjernen af sproget L(A₁) er derfor sproget af alle ord, der består af par 00 og 11, for eksempel 0000, 110011, 11110000 osv. Automaten, der ville acceptere denne Kleene-stjerne, ville vi konstruere ved at oprette en ny starttilstand q_s med en epsilon-overgang til den tidligere starttilstand q₀ og tilføje epsilon-overgange fra tilstandene q₃ og q₄ til tilstanden q₀:

Vi kan kontrollere, at denne automat virkelig accepterer ordene 0000, 110011, 11110000, men for eksempel ikke ordet 1010.

Kilder

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools