7738996292

Rozdział 2

Słowa nieskończone

Spisali: Piotr Szczepański i Krzysztof Kąs

Słowa nieskończone mogą przyjmować różne formy:

1.    A* uj = {0,1,2,3...} np : abababdba...

2.    A^z np : ... abababdba...

3.    .4^R

Nas będą interesować jedynie słowa postaci A^u.

2.1 Twierdzenie Biichiego

Twierdzenie 3 (Buchiego). Dla języka L C A^w następujące warunki są równoważne:

1.    L jest definiowalny w logice MSO.

2.    L jest rozpoznawany przez niedeterministyczny automat z warunkiem Buchiego.

3.    L można opisać wyrażeniem uj-regulamym.

Język spełniający trzy warunki z powyższego twierdzenia nazwiemy w-regularnym.

Dowód powyższego twierdzenia przedstawimy w rozdziale 2.2. Najpierw wyjaśnimy występujące w twierdzeniu pojęcia.

Definicja 1. Wyrażeniem u>regularnym nazwiemy skończoną sumę postaci

U w

gdzie Li, Ki C A* regularne języki słów skończonych. Dodatkowo przyjmiemy, że = 0.

Ostanie zdanie może budzić lekki niepokój, gdyż e* = {e}. Przyjęcie e" = 0 ułatwi nam obchodzenie się z wyrażeniami w-regularnymi.

Poniżej podamy kilka przykładów wyrażeń regularnych wraz z odpowiadającą im formułą MSO:

•    A“aA^ul odpowiada 3_xa(x)

•    (A*a)^M odpowiada V_y3_x>ya(x)

•    (A*ba*b)^UJ odpowiada V_x3_s>a;6(j/) A 3_z>yb(z) A V„y < u < z => a(u)