Aby do ABBY

18 maja 2012
Marek Penszko

Poczytuję ostatnio o lingwistyce matematycznej, a ściślej – o językach formalnych. To temat ciekawy i dość przystępny, choć bardzo rzadko poruszany w lżejszej formie. W Polsce ukazała się chyba tylko jedna książka popularnonaukowa, w której jest krótki rozdział o gramatyce formalnej – Granice rozumu A.K. Dewdneya (2005). W sieci znalazłem też polską stronę z interesującym i zrozumiałym dla maluczkich opisem podstawowych zagadnień. Wspominam o tym, bo języki formalne są trochę łamigłówkowe.

Mamy dwa słowa – np. AJEDREZ i SAKK – oraz zagadkę: czy pochodzą one z jednego, czy z dwu różnych języków naturalnych? Kto nie jest lingwistą, musi sięgnąć do źródeł, bo odpowiedź „na czuja” często jest loterią, zwłaszcza gdy języki należą do tej samej rodziny. W przypadku języków formalnych – nawet opartych na najskromniejszym 2-literowym alfabecie, czyli przypominającym system dwójkowy – sprawa też bywa nieprosta, ale przynajmniej istnieje metoda, pewien schemat dochodzenia do odpowiedzi na pytanie o wspólnotę językową pary słów.

Oto dwa słowa:
(1) BBABB
(2) ABBA
Oba należą do jednego języka wówczas, jeżeli jedno z nich można przekształcić w drugie, korzystając z gramatyki przejściowej, która w tym przypadku wygląda tak:
(a) A -> BAA
(b) AAB -> A
(c) BBA -> AB
Oznacza to, że wychodząc od słowa (1) należy w kolejnych krokach wymieniać litery lub grupy liter (podsłowa) na inne – zgodnie z gramatyką – dotąd, aż powstanie słowo (2). Na przykład, dokonując w (1) najpierw podmiany (a), a potem (c), początek metamorfozy wyglądałby tak (wymieniane litery są wyróżnione):
BBABB > BBBAABB > BABABB > …

Zadanie polega na dotarciu od (1) do (2) w minimalnej liczbie kroków.

Komentarze z prawidłowymi rozwiązaniami uwalniane są wieczorem w przeddzień kolejnego wpisu. Wpisy pojawiają się co kilka dni.