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



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

Wartością funkcji (q,a), aT jest zbiór stanów, do których automat może przejść startując ze stanu q przy wejściu będącym pojedynczym symbolem a. Wartością funkcji jest zbiór stanów, do których automat startując ze stanu q może przejść po przetworzeniu łańcucha w. Dlatego też – jeśli nie będzie to prowadzić do niejednoznaczności – będziemy dalej stosować symbol zarówno do oznaczenia funkcji przejścia, jak i domknięcia (uogólnienia) funkcji przejścia (opuszczając daszek).
Tw. Myhilla-Nerode’a:

Następujące warunki są równoważne:

(1) Język LT* jest akceptowany przez pewien deterministyczny automat skończony.

(2) Język L jest sumą teoriomnogościową pewnych klas abstrakcji pewnej prawostronnie niezmienniczej relacji równoważności o indeksie skończonym.

(3) Relacja RL indukowana przez ten język L jest relacją o indeksie skończonym.
Szkic uzasadnienia twierdzenia będzie pokazywał spełnienie następujących implikacji (1)(2)(3)(1).
(1)(2)

Niech A=0,> będzie deterministycznym automatem skończonym akceptującym język L. Zdefiniujemy relację RA T*T* taką, że xRAy (q0,x)=(q0,y). Relacja RA jest relację prawostronnie niezmienniczą, gdyż dla dowolnych x i y, jeśli xRAy, tzn. (q0,x)=(q0,y), to dla dowolnego słowa z



(q0,xy)=((q0,x),z)=((q0,y),z)=(q0,yz)

Relacja RA jest też relacją równoważności (proszę sprawdzić). Relacja RA jest relacją o indeksie skończonym, ponieważ indeks relacji (liczba klas równoważności) nie przekracza liczby stanów automatu A. Wynika to z faktu, że dowolne dwa słowa, dla których przetwarzanie kończy się w tym samym stanie, są ze sobą w relacji RA. Wynika z tego, że zbiór wszystkich słów, dla których przetwarzanie kończy się w pewnym stanie, zawiera się w pewnej klasie abstrakcji relacji RA. Tak określone zbiory słów stanowią podział zbioru wszystkich słów nad alfabetem T. Co więcej zbiory te są klasami abstrakcji, gdyż dowolne dwa słowa, dla których przetwarzanie przez automat kończy się w różnych stanach, nie są ze sobą w relacji RA.

Oczywiście język L jest sumą zbiorów tych słów, dla których przetwarzanie kończy się w stanach akceptujących automatu A.

(2)(3)


Niech będzie prawostronnie niezmienniczą relacją równoważności o indeksie skończonym. Niech język L będzie sumą pewnych klas abstrakcji relacji . Pokażemy, że każda klasa abstrakcji relacji jest zawarta w pewnej klasie abstrakcji relacji RL indukowanej przez język L. Niech x,yT* i niech xy (co oczywiście oznacza, że x i y należą do tej samej klasy abstrakcji relacji ). Wobec tego (zT*) xz  yz – na mocy prawostronnej niezmienniczości relacji . To znaczy, że dla dowolnego zT* oba słowa xz i yz należą do jakiejś jednej klasy abstrakcji. Ponieważ język L jest sumą teoriomnogościową pewnych klas abstrakcji relacji , to dla danego słowa z albo oba słowa xz i yz należą do języka L, albo oba słowa nie należą do języka L. To wyczerpuje definicję relacji RL indukowanej przez język L. Ostatecznie dla dowolnych słów x i y, jeżeli pozostają w relacji , to pozostają też w relacji RL. Czyli każda klasa abstrakcji relacji zawiera się w pewnej klasie abstrakcji relacji RL, co oznacza, że indeks relacji RL jest nie większy niż indeks relacji , czyli skończony.

(3)(1)


Niech L będzie językiem nad alfabetem T, niech RL będzie relacją o indeksie skończonym indukowaną przez język L. Następujący automat będzie akceptował język L:

A=0,>

gdzie:


  • zbiór stanów Q jest zbiorem indeksowanym klasami abstrakcji relacji RL,

  • stanem początkowym q0 jest stan indeksowany klasą abstrakcji zawierającą słowo puste q[],

  • stanami akceptującymi są stany indeksowane klasami abstrakcji zawartymi w języku L,

  • funkcja przejścia jest zdefiniowana następująco: (q[w],a)=q[wa], gdzie wT*, aT oraz [w] i [wa] są klasami abstrakcji o reprezentantach w i wa.

Tak skonstruowany automat A jest automatem skończonym deterministycznym akceptującym język L.
Z twierdzenia Myhilla-Nerode’a wynika, że relacja RL jest relacją o najmniejszym indeksie spośród relacji prawostronnie niezmienniczych definiujących język L (tzn. takich, dla których suma pewnych klas abstrakcji pokrywa się z językiem L). Tak więc automat skonstruowany na podstawie relacji RL będzie deterministycznym automatem akceptującym język L minimalnym ze względu na liczbę stanów.

1   2   3


©operacji.org 2017
wyślij wiadomość

    Strona główna