Säännöllisten kielten leikkaus

Olkoon meillä kaksi säännöllistä kieltä L₁, L₂. Todistamme, että niiden leikkaus L = L₁ ∩ L₂ on myös säännöllinen kieli.

Todistuksen idea

Meillä on kaksi säännöllistä kieltä L₁ ja L₂, ja haluamme todistaa, että niiden leikkaus L₁ ∩ L₂ on jälleen säännöllinen kieli. Koska L₁ ja L₂ ovat säännöllisiä kieliä, on olemassa äärelliset automaatit A₁ ja A₂, jotka hyväksyvät kielet L₁ ja L₂, eli pätee L(A₁) = L₁ ja L(A₂) = L₂. Rakennamme seuraavaksi äärellisen automaatin A, joka hyväksyy kielen L₁ ∩ L₂, ja todistamme näin, että kieli L₁ ∩ L₂ on säännöllinen.

Sana kuuluu kielten leikkaukseen, jos se kuuluu kieleen L₁ ja samalla kieleen L₂. Sanan täytyy siis kuulua sekä automaatin A₁ että automaatin A₂ hyväksymiin. Käytämme täsmälleen samaa ideaa kuin säännöllisten kielten yhdisteessä, muutamme vain lopputilojen joukkoa.

Menetelmän formalisointi

Meillä on kaksi automaattia,

$$\begin{array}{rcl}{A}_1& =& (Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_0,F_1)\\ A_2& =& (Q_2,{\mathrm{\Sigma }}_2,{\delta }_2,p_0,F_2)\end{array}$$

Rakennamme automaatin A = (Q, Σ, δ, q, F), joka hyväksyy kielen L(A₁) ∩ L(A₂). Pätee, että

• Q = Q₁ × Q₂
• Σ= Σ₁ ∩ Σ₂
• q = (q₀, p₀)
• F = F₁ × F₂

Siirtymäfunktiolle δ pätee seuraava yhtälö:

$$\mathrm{\forall }q\in Q_1,p\in Q_2:\delta ((q,p),a)=({\delta }_1(q,a),{\delta }_2(p,a))$$

Esimerkki

Olkoon meillä tämä automaatti A₁, joka hyväksyy kaikki sanat, joissa on parillinen määrä ykkösiä:

ja automaatti A₂, joka hyväksyy sanat, joissa on pariton määrä nollia:

Rakennamme automaatin, joka hyväksyy näiden kielten leikkauksen. Tämän automaatin tilojen joukko on Q = Q₁ × Q₂, alkutila on tila (q₀, p₀) ja lopputilat ovat F₁ × F₂:

Sitten viimeistelemme siirtymät niin, että δ((q, p), a) = (δ₁(q, a), δ₂(p, a)):

Tässä automaatissa on esimerkiksi tilasta (q₀, p₀) symbolille 0 siirtymä tilaan (q₀, p₁). Se tarkoittaa, että automaatilla A₁ on tilasta q₀ symbolille 0 siirtymä takaisin tilaan q₀. Automaatilla A₂ taas on symbolille 0 siirtymä tilasta p₀ tilaan p₁.

Automaattia voi kokeilla. Sen pitäisi hyväksyä sanat kuten 110 tai 00000 (niissä on parillinen määrä ykkösiä ja samalla pariton määrä nollia), mutta sen ei pitäisi hyväksyä sanoja kuten 11, 111, 1010.

Lähteet

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