Kleene-stjernen til et regulært språk

Vi har et regulært språk L. Vi skal bevise at Kleene-stjernen til språket L igjen er et regulært språk.

Hva Kleene-stjernen til et språk er

Kleene-stjernen til språket L betegner vi L^∗. Den inneholder alle ord som kan settes sammen ved å koble sammen et endelig antall ord fra språket L. Vi kan definere den som:

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

der ∘ betegner operasjonen konkatenering. Kleene-stjernen inneholder også det tomme ordet, altså ϵ.

Formell framgangsmåte

Vi går fram veldig likt som i tilfellet konkatenering av språk. Men i stedet for å koble sammen to ulike automater kobler vi sammen én automat — fra sluttilstandene i automaten lar vi altså epsilonoverganger gå til starttilstanden i automaten. Kleene-stjernen må imidlertid også inneholde det tomme ordet. Hvordan ordner vi det? Vi kan gjøre starttilstanden til en sluttilstand. Da ville en slik automat akseptere det tomme ordet, men den kunne også akseptert noen andre ord. Derfor lager vi i stedet en ny starttilstand og lar en epsilonovergang gå fra denne nye starttilstanden til den opprinnelige starttilstanden.

Vi har et regulært språk L₁ og en automat som aksepterer dette språket:

$$\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⟩ som oppfyller:

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

Overgangsfunksjonen δ definerer vi slik:

$$\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

La oss ha denne automaten A₁, som aksepterer ordene 00 eller 11:

Kleene-stjernen til språket L(A₁) er altså språket av alle ord som består av parene 00 og 11, for eksempel 0000, 110011, 11110000 osv. Automaten som skulle akseptere denne Kleene-stjernen, ville vi konstruert ved å lage en ny starttilstand q_s med en epsilonovergang til den tidligere starttilstanden q₀ og legge til epsilonoverganger fra tilstandene q₃ og q₄ til tilstanden q₀:

Vi kan kontrollere at denne automaten virkelig aksepterer 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