4 Własności języków regularnych



Pobieranie 194,35 Kb.
Strona1/3
Data23.10.2017
Rozmiar194,35 Kb.
  1   2   3

4.4. Własności języków regularnych
Jeśli jakiś język jest regularny, to jest on akceptowany przez deterministyczny automat skończony o pewnej określonej liczbie stanów. Załóżmy, że ta liczba stanów wynosi k. Rozważamy słowo należące do tego języka. Słowo to ma długość k lub więcej symboli. Słowo to jest akceptowane przez nasz deterministyczny automat skończony posiadający k stanów. Aby było ono zaakceptowane, automat startując ze stanu początkowego musi przeczytać co najmniej k symboli i zatrzymać się w pewnym stanie końcowym akceptującym. Słowo wyznacza więc w grafie automatu ścieżkę końcową o liczbie krawędzi co najmniej k. Wobec tego liczba stanów (węzłów grafu), które znajdują się na ścieżce końcowej wyznaczonej przez to słowo w grafie automatu, wynosi co najmniej k+1. Ponieważ jednak automat posiada tylko k stanów, co najmniej jeden stan na ścieżce wyznaczonej przez słowo musi się powtórzyć (musimy dwukrotnie przejść przez co najmniej jeden węzeł grafu). Przechodząc dwukrotnie przez jakiś węzeł (stan) robimy pętlę. Moglibyśmy przejść przez tę pętlę więcej niż jeden raz – w rzeczywistości tyle razy, ile chcemy. Moglibyśmy też nie wchodzić w tę pętlę ani razu – i zawsze doszlibyśmy do stanu akceptującego. Właśnie pokazaliśmy w sposób uproszczony, że jeśli mamy wystarczająco długie słowo akceptowane przez automat skończony, to możemy znaleźć podłańcuch tego słowa (naszą „pętlę”) położony blisko początku tego słowa, który może być „napompowany”, tj. powtórzony tyle razy, ile chcemy, a wynikowe słowo będzie akceptowane przez ten automat skończony.
Lemat o pompowaniu języków regularnych

Niech L będzie językiem regularnym. Wtedy istnieje stała k, taka że jeśli w jest dowolnym słowem z L oraz |w|k, to w możemy przedstawić w postaci w = xuz, gdzie |xu| ≤ k, |u| ≥ 1, oraz xuiz należy do L dla każdego i ≥ 0. Co więcej, k nie jest większe niż liczba stanów najmniejszego automatu skończonego akceptującego L.

Formalnie można to zapisać jak niżej.

Tw.: Jeśli L jest językiem regularnym to  k : (w  L  |w|  k)  (w = xuz  |xu|  k  |u| ≥ 1  i  0 : xuiz  L)
Warto zauważyć, że lemat o pompowaniu mówi, że jeśli język regularny zawiera długie słowo xuz, to zawiera nieskończony zbiór słów postaci xuiz. Lemat wykorzystujemy do udowodnienia następującego twierdzenia:

Tw.: Zbiór słów akceptowanych przez deterministyczny automat skończony A o k stanach jest:

(a) niepusty wtedy i tylko wtedy, gdy A akceptuje słowo o długości mniejszej od k;

(b) nieskończony wtedy i tylko wtedy, jeśli A akceptuje słowo o długości l, gdzie k ≤ l < 2k.

Ad. (a). Jeśli zbiór zawiera jakieś słowo, to jest on w sposób oczywisty niepusty. Odwrotnie, jeśli A akceptuje zbiór niepusty, to pokażemy, że musi akceptować słowo o długości mniejszej od k. Niech w będzie akceptowanym słowem, nie dłuższym od żadnego innego akceptowanego słowa. Na mocy lematu o pompowaniu, długość w musi być mniejsza od k, gdyż gdyby w było najkrótsze i |w| ≥ k, to mielibyśmy w = xuz i xz byłoby słowem akceptowanym krótszym od w.

Ad. (b). Jeśli w należy do L(A) i k ≤ |w| < 2k, to na mocy lematu o pompowaniu L(A) jest nieskończony, ponieważ w = xuz oraz xuiz należy do L(A) dla każdego i. Odwrotnie, jeśli L(A) jest nieskończony, to istnieje w należące do L(A), takie że |w| ≥ k. Jeśli |w| < 2k, to dowód jest zakończony. Pokażemy teraz, że L(A) musi zawierać słowo o długości mniejszej od 2k i nie mniejszej od k. Przypuśćmy, że tak nie jest, czyli L(A) nie zawiera słowa o długości pomiędzy k a 2k–1. Niech więc w będzie słowem z L(A) o długości co najmniej 2k, ale nie dłuższym od żadnego słowa z L(A) posiadającego długość nie mniejszą od 2k. Stosując ponownie lemat o pompowaniu możemy zapisać w jako w = xuz, gdzie 1 ≤ |u| ≤ k i xz należy do L(A). Zatem, albo w nie jest najkrótszym ze słów o długości nie mniejszej od 2k, albo też |xz| leży pomiędzy k a 2k–1. W obu przypadkach dostajemy sprzeczność.
Przykład: Czy język { aibjci+j i1, j1 } jest językiem regularnym?

Nie; przypuśćmy dla dowodu nie wprost, że język ten jest regularny i niech k będzie stałą z lematu o rozrastaniu języków regularnych. Rozważamy słowo w = akbkc2k = xuz. Słowo w ma długość równą 4k>k. Wówczas u może zawierać od jednej do maksymalnie k liter a (przypadek (1)) lub u może zawierać od jednej do maksymalnie k liter b (przypadek (2)) lub u może zawierać od jednej do maksymalnie k liter c (przypadek (3)). Wybranie u w inny sposób spowoduje, że przy rozrastaniu ui pojawią się "przeplatanki" symboli, np. abab... lub bcbc... Rozważymy łańcuch xu2z. W przypadku (1) zawiera on co najmniej k+1 i co najwyżej 2k liter a. Wówczas xu2z nie należy do języka, gdyż liczba liter b pozostaje bez zmiany, zaś liter c jest zbyt mało. Analogicznie rozpatrujemy przypadek (2). W przypadku (3) łańcuch xu2z zawiera co najmniej 2k+1 i co najwyżej 3k liter c, zaś liczba liter a oraz b pozostaje bez zmiany, jest więc za dużo liter c i słowo xu2z także nie należy do języka. Tak więc xu2z w żadnym możliwym przypadku nie należy do naszego języka, język ten nie może być regularny.


Tw.: Klasa języków regularnych jest zamknięta ze względu na sumę teoriomnogościową, złożenie oraz domknięcie Kleene’go. Formalnie, jeśli L1 i L2 są językami regularnymi, to językami regularnymi są także L1  L2, L1 L2, L1*.

Uzasadnienie wynika natychmiast z definicji języka (zbioru) regularnego.


Tw.: Klasa języków regularnych jest zamknięta ze względu operację dopełnienia. Formalnie, jeśli język L jest językiem regularnym, gdzie L T*, to język = T* – L też jest językiem regularnym.

Jeżeli język L jest językiem regularnym, to istnieje deterministyczny zupełny automat skończony A akceptujący ten język. Jeżeli w tym automacie stany akceptujące zmienimy na nieakceptujące i na odwrót, to otrzymamy automat akceptujący słowa nie należące do języka L i tylko takie słowa. Zatem automat A będzie akceptował dopełnienie języka L, a więc dopełnienie musi być językiem regularnym.


Tw.: Klasa języków regularnych jest zamknięta ze względu na iloczyn teoriomnogościowy. Formalnie, jeśli L1 i L2 są językami regularnymi, to językami regularnymi jest także L1  L2.

Zamkniętość ze względu na iloczyn teoriomnogościowy wynika z zamkniętości ze względu na sumę teoriomnogościową oraz dopełnienie.





Tw.: Klasa języków regularnych jest zamknięta ze względu na operację podstawienia (w tym także homomorfizmu).
Tw.: Klasa języków regularnych jest zamknięta ze względu na przeciwobrazy homomorficzne.
Tw.: Klasa języków regularnych jest zamknięta ze względu na ilorazy (dzielenie przez dowolne zbiory).
Definicja domknięcia funkcji przejścia automatu skończonego (niedeterministycznego, z ‑ruchami):

Domknięciem funkcji przejścia automatu skończonego : Q ( T {}) 2Q nazywamy funkcję:



taką, że:



  1   2   3


©operacji.org 2017
wyślij wiadomość

    Strona główna