{"id":3587,"date":"2012-05-18T00:25:53","date_gmt":"2012-05-17T22:25:53","guid":{"rendered":"http:\/\/penszko.blog.polityka.pl\/?p=3587"},"modified":"2012-05-18T00:25:53","modified_gmt":"2012-05-17T22:25:53","slug":"aby-do-abby","status":"publish","type":"post","link":"https:\/\/blog.polityka.pl\/penszko\/2012\/05\/18\/aby-do-abby\/","title":{"rendered":"Aby do ABBY"},"content":{"rendered":"

Poczytuj\u0119 ostatnio o lingwistyce matematycznej, a \u015bci\u015blej – o j\u0119zykach formalnych. To temat ciekawy i do\u015b\u0107 przyst\u0119pny, cho\u0107 bardzo rzadko poruszany w l\u017cejszej formie. W Polsce ukaza\u0142a si\u0119 chyba tylko jedna ksi\u0105\u017cka popularnonaukowa, w kt\u00f3rej jest kr\u00f3tki rozdzia\u0142 o gramatyce formalnej – Granice rozumu<\/em> A.K. Dewdneya (2005). W sieci znalaz\u0142em te\u017c polsk\u0105 stron\u0119<\/a> z interesuj\u0105cym i zrozumia\u0142ym dla maluczkich opisem podstawowych zagadnie\u0144. Wspominam o tym, bo j\u0119zyki formalne s\u0105 troch\u0119 \u0142amig\u0142\u00f3wkowe.<\/p>\n

Mamy dwa s\u0142owa – np. AJEDREZ i SAKK – oraz zagadk\u0119: czy pochodz\u0105 one z jednego, czy z dwu r\u00f3\u017cnych j\u0119zyk\u00f3w naturalnych? Kto nie jest lingwist\u0105, musi si\u0119gn\u0105\u0107 do \u017ar\u00f3de\u0142, bo odpowied\u017a „na czuja” cz\u0119sto jest loteri\u0105, zw\u0142aszcza gdy j\u0119zyki nale\u017c\u0105 do tej samej rodziny. W przypadku j\u0119zyk\u00f3w formalnych – nawet opartych na najskromniejszym 2-literowym alfabecie, czyli przypominaj\u0105cym system dw\u00f3jkowy – sprawa te\u017c bywa nieprosta, ale przynajmniej istnieje metoda, pewien schemat dochodzenia do odpowiedzi na pytanie o wsp\u00f3lnot\u0119 j\u0119zykow\u0105 pary s\u0142\u00f3w.<\/p>\n

Oto dwa s\u0142owa:
\n(1) BBABB
\n(2) ABBA
\nOba nale\u017c\u0105 do jednego j\u0119zyka w\u00f3wczas, je\u017celi jedno z nich mo\u017cna przekszta\u0142ci\u0107 w drugie, korzystaj\u0105c z gramatyki przej\u015bciowej, kt\u00f3ra w tym przypadku wygl\u0105da tak:
\n(a) A -> BAA
\n(b) AAB -> A
\n(c) BBA -> AB
\nOznacza to, \u017ce wychodz\u0105c od s\u0142owa (1) nale\u017cy w kolejnych krokach wymienia\u0107 litery lub grupy liter (pods\u0142owa) na inne – zgodnie z gramatyk\u0105 – dot\u0105d, a\u017c powstanie s\u0142owo (2). Na przyk\u0142ad, dokonuj\u0105c w (1) najpierw podmiany (a), a potem (c), pocz\u0105tek metamorfozy wygl\u0105da\u0142by tak (wymieniane litery s\u0105 wyr\u00f3\u017cnione):
\nBBA<\/strong><\/em>BB > BBBA<\/em><\/strong>ABB > BABABB > …<\/p>\n

Zadanie polega na dotarciu od (1) do (2) w minimalnej liczbie krok\u00f3w.<\/p>\n

Komentarze z prawid\u0142owymi rozwi\u0105zaniami uwalniane s\u0105 wieczorem w przeddzie\u0144 kolejnego wpisu. Wpisy pojawiaj\u0105 si\u0119 co kilka dni.<\/sub><\/em><\/p>\n","protected":false},"excerpt":{"rendered":"

Poczytuj\u0119 ostatnio o lingwistyce matematycznej, a \u015bci\u015blej – o j\u0119zykach formalnych. To temat ciekawy i do\u015b\u0107 przyst\u0119pny, cho\u0107 bardzo rzadko poruszany w l\u017cejszej formie. W Polsce ukaza\u0142a si\u0119 chyba tylko jedna ksi\u0105\u017cka popularnonaukowa, w kt\u00f3rej jest kr\u00f3tki rozdzia\u0142 o gramatyce formalnej – Granice rozumu A.K. Dewdneya (2005). W sieci znalaz\u0142em te\u017c polsk\u0105 stron\u0119 z interesuj\u0105cym […]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/3587"}],"collection":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/comments?post=3587"}],"version-history":[{"count":16,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/3587\/revisions"}],"predecessor-version":[{"id":3605,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/posts\/3587\/revisions\/3605"}],"wp:attachment":[{"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/media?parent=3587"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/categories?post=3587"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.polityka.pl\/penszko\/wp-json\/wp\/v2\/tags?post=3587"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}