spyked bricks in the wall

o problemă de lingvistică

Lingvistica este, după cum probabil bine cunoașteți, o știință care se ocupă cu studiul limbilor. Mai clar exprimat, aceasta studiază limbajele, fie ele naturale sau artificiale ori destinate uzului de către om sau mașină. Astfel în acest articol nu vom vorbi despre organul fizic și biologic care este limba și nici despre tehnici ale artei sexului care se folosesc de acesta. Dat fiind mai ales faptul că știința lingvisticii este extrem de vastă, fiind compusă din arii care nu-s musai relevante pentru problema ce urmează să o descriu, mă voi limita la a trata doar câteva din aspectele formale într-un mod cvasi-formal.

Putem începe deci a formula problema noastră cu formula standard „fie un limbaj ”. În primul rând că are asociat un alfabet , adică mai exact o mulțime de simboluri pe care noi le vom numi litere, ca-n limbile de zi cu zi. Vom nota cu mulțimea șirurilor de litere peste limbajul . Astfel, în urma analizei lexicale, un compilator oarecare – pe care noi îl vom numi mai generic translator – va putea să ia șiruri de litere și să le asocieze cu cuvinte din limbaj, care-s analogul abstract al cuvintelor din limbile de zi cu zi.

Următoarea etapă constă în prelucrarea cuvintelor obținute în primă fază conform unor reguli care stabilesc logica limbajului. Vom nota cu mulțimea cuvintelor aparținând lui – adică dicționarul sau vocabularul asociat limbajului – și bineînțeles cu mulțimea șirurilor de cuvinte. Observăm că dacă notăm cu mulțimea cuvintelor din de lungime , atunci și , unde e lungimea maximă a cuvintelor din . Deci reprezintă mulțimi disjuncte de cuvinte care alcătuiesc mulțimea cuvintelor limbajului .

Observăm de asemenea că pentru a separa cuvintele brute aflate în șirurile din avem nevoie de o literă specială. Limbajul natural se folosește de spații și semne de punctuație, însă noi vom utiliza un simbol generic notat cu , care e suficient pentru limbajul nostru. Putem însă accepta și alte simboluri în cazul în care acestea au un impact asupra sintaxei.

Mai departe vom afirma că are o structură sintactică bine definită și eventual o semantică. Rămâne să vedem ce rol o să aibă acestea, dacă o să aibă vreunul – nu știm exact și e posibil să nu putem da un răspuns în sensul ăsta. De asemenea știm că limbajele formale sunt izomorfe cu monoizii liberi, iar între aceștia din urmă se pot defini morfisme, al căror analog în domeniul calculatoarelor este compilatorul/interpretorul, în limbajul natural acesta purtând pur și simplu numele de translator.

În formalismul definit mai sus putem să formulăm foarte ușor problema dată de Mihai în cadrul concursului de programare: fiind date , un cuvânt (cuvântul sursă) și un cuvânt (cuvântul destinație), să se găsească un șir ordonat de cuvinte din de forma cu proprietatea că distanța Levenshtein între oricare două cuvinte consecutive este 1. Bineînțeles, se pune problema șirului de lungime minimă etc. În particular se observă că transformările între cuvinte sunt endomorfisme în sensul în care păstrează vocabularul lui , iar sintaxa și semantica nu ne interesează.

Problema pe care doresc să o formulez e însă foarte diferită de cea a lui Mihai. Nu ne interesează distanța între cuvinte și nici dacă cuvintele noi formate sunt în . Vrem însă să putem face afirmații cu privire la fonetica noilor cuvinte, raportându-ne la cele vechi. Formularea problemei este astfel:

Fiind dat un limbaj ca mai sus, să se găsească limbajele care să păstreze alfabetul și fonetica lui , și morfisme între și .

Mai exact trebuie să aibă următoarele proprietăți:

• (a) ;
• (b) (am notat cu mulțimea fonemelor lui );
• (c) , familie de morfisme, și
• (d) .

(a) e banală. (b) e destul de simplă, referindu-se la faptul că nu dorim să adăugăm sau să scoatem foneme din limbaj și nici să modificăm sensul acestora în raport cu simbolurile din , deci unele litere sau grupuri de litere vor trebui păstrate în cadrul limbajului. (c) impune existența unor morfisme care să ducă din cuvintele lui în cele ale lui , păstrând lungimea acestora (cam asta e singura restricție în comun cu cele din Word Ladder).

(d) e un pic mai ciudată. este un predicat logic cu semnificația „cuvântul poate fi pronunțat”. e o necunoscută în problema noastră, în sensul că mi se pare destul de greu de cuantificat dificultatea pronunției unui cuvânt într-un limbaj dat în care se cunosc asocierile foneme-gramatică/foneme-semantică. În orice caz în fonetica limbii române „îp” mi se pare un cuvânt pronunțabil pe când „tt” nu. Deci dacă e un cuvânt din , iar e un cuvânt din obținut prin aplicarea lui asupra lui , atunci trebuie să poată fi pronunțat.

Specificația de mai sus e foarte generală, astfel că poate fi modificată în chip și fel. De exemplu eu nu am pus restricții asupra lungimii cuvintelor, deci pot exista teoretic o infinitate de funcții , lucru nepractic în cazul limbajului natural. De asemenea nu am spus nimic despre natura funcțiilor . Ele pot fi definite parțial sau total pe cuvintele din sau pot fi chiar bijective, caz în care ar putea de exemplu să meargă până la a păstra semantica limbajului inițial, sau în orice caz ar fi interesant de verificat dacă se întâmplă asta.

Pe de altă parte problema ar putea fi extinsă prin includerea unor reguli explicite de transformare la nivelul sintaxei. Mai mult, nu văd de ce fonemele nu ar putea fi înlocuite cu o structură asemănătoare, care eventual ar avea mai mult sens pentru lingvistica computațională. O astfel de abordare și-ar dovedi foarte tare utilitatea în domeniul metaprogramării, unde obiectul muncii reprezintă efectiv limbajele.

În fine, mi se pare că problema ar putea fi interesantă inclusiv din punctul de vedere al algoritmicii. Nu îmi e clar ce algoritm ar putea să rezolve în mod optim problema, dar sunt aproape sigur că nu se poate găsi o soluție în timp polinomial. De fapt anumite variațiuni s-ar putea să nu admită soluții, deci însăși problema asta le-ar putea da de lucru indivizilor preocupați de lingvistică și de știința calculatoarelor.