Kleenestjärnan av ett reguljärt språk

Vi har ett reguljärt språk L. Vi bevisar att Kleenestjärnan av språket L också är ett reguljärt språk.

Vad är Kleenestjärnan av ett språk

Kleenestjärnan av språket L betecknas L^∗. Den innehåller alla ord som kan sättas ihop genom att konkatenera ett ändligt antal ord från språket L. Vi kan definiera Kleenestjärnan som:

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

där ∘ betecknar konkatenering. Kleenestjärnan innehåller också det tomma ordet, dvs. ϵ.

Formell metod

Vi går till väga på ett sätt som påminner mycket om konkatenering av språk. Men i stället för att koppla ihop två olika automater kopplar vi ihop en enda automat – från automatens sluttillstånd drar vi epsilonövergångar till automatens starttillstånd. Kleenestjärnan måste dock också innehålla det tomma ordet. Hur ordnar vi det? Vi kan göra starttillståndet till ett sluttillstånd. Då skulle automaten acceptera det tomma ordet, men den skulle också kunna acceptera något annat ord. Därför skapar vi i stället ett nytt starttillstånd och drar en epsilonövergång från det nya starttillståndet till det ursprungliga starttillståndet.

Vi har ett reguljärt språk L₁ och en automat som accepterar språket:

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

Vi konstruerar en icke-deterministisk automat A = ⟨Q, Σ, δ, q_s, F⟩ för vilken det gäller att:

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

Övergångsfunktionen δ definierar vi så här:

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

Exempel

Låt oss ta den här automaten A₁, som accepterar orden 00 eller 11:

Kleenestjärnan av språket L(A₁) är alltså språket av alla ord som består av par 00 och 11, till exempel 0000, 110011, 11110000 osv. En automat som accepterar den här Kleenestjärnan konstruerar vi genom att skapa ett nytt starttillstånd q_s med en epsilonövergång till det tidigare starttillståndet q₀ och lägga till epsilonövergångar från tillstånden q₃ och q₄ till tillståndet q₀:

Vi kan kontrollera att den här automaten verkligen accepterar orden 0000, 110011, 11110000, men till exempel inte ordet 1010.

Källor

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