Затваряне на регулярен език

Имаме регулярен език L. Ще докажем, че затварянето на езика L е отново регулярен език.

Какво е затваряне на език

Затварянето на езика L означаваме с L^∗. Затварянето съдържа всички думи, които могат да се получат чрез конкатенация на краен брой думи от езика L. Затварянето можем да определим като:

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

където ∘ означава операцията конкатенация. Затварянето съдържа и празната дума, т.е. ϵ.

Формален метод

Ще действаме много подобно на случая с конкатенацията на езици. Само че вместо да свързваме два различни автомата, свързваме един автомат — от крайните състояния на автомата водим ε-преходи към началното състояние на автомата. Затварянето обаче трябва да съдържа и празната дума. Как да го уредим? Можем да направим началното състояние крайно. Тогава такъв автомат би приел празната дума, но би могъл да приеме и някоя друга дума. Затова вместо това създаваме ново начално състояние и от това ново начално състояние водим ε-преход към първоначалното начално състояние.

Имаме регулярен език L₁ и автомат, който приема този език:

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

Построяваме недетерминиран автомат A = ⟨Q, Σ, δ, q_s, F⟩, за който е в сила:

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

Преходната функция δ определяме така:

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

Пример

Нека имаме този автомат A₁, който приема думите 00 или 11:

Затварянето на езика L(A₁) е следователно езикът на всички думи, които се състоят от двойки 00 и 11, например 0000, 110011, 11110000 и т.н. Автомата, който би приемал това затваряне, бихме построили така, че да създадем ново начално състояние q_s с ε-преход към бившето начално състояние q₀ и да добавим ε-преходи от състоянията q₃ и q₄ към състоянието q₀:

Можем да проверим, че този автомат наистина приема думите 0000, 110011, 11110000, но не приема например думата 1010.

Източници

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