Diferența limbajelor regulate
Fie două limbaje regulate L1, L2. Vom demonstra că diferența lor L = L1 ∖ L2 este, de asemenea, un limbaj regulat.
Ideea
De fapt nu prea avem ce demonstra. Pentru diferența a două mulțimi avem relația:
unde L2′ este complementul limbajului L2. Din capitolele despre intersecția limbajelor regulate și despre complementul unui limbaj regulat știm că limbajele regulate sunt închise la ambele operații. Asta înseamnă că putem construi un automat care acceptă intersecția a două limbaje și un automat care acceptă complementul unui limbaj. Putem folosi aceste automate pentru a construi automatul care va accepta limbajul L1 ∩ L2′, care este însă, totodată, limbajul L1 ∖ L2.
Exemplu
Fie automatul A1, care acceptă toate cuvintele ce conțin un număr par de 1:
și automatul A2, care acceptă cuvintele ce conțin un număr impar de 0:
Construim automatul care va accepta diferența acestor limbaje. Avem nevoie așadar de automatul A2′, care va fi complementul automatului A2. Doar interschimbăm stările finale cu cele nefinale:
Acum construim automatul A, care va accepta intersecția limbajelor L(A1) și L(A2′):
Surse
Capitole: Închiderea la operații, Reuniunea, Intersecția, Diferența, Complementul, Concatenarea, Închiderea Kleene
