Формалните езици — невидимата граматика на дигиталния свят
Формалните езици —
невидимата граматика на дигиталния свят
Компютрите изглеждат все по-„умни" — превеждат, разпознават глас, отговарят на въпроси. Но зад всяко тяхно действие не стои разбиране, а нещо съвсем различно: строга формална обработка на символи. Историята на тази идея започва преди повече от триста години с мечтата на Лайбниц и достига до машината на Тюринг, йерархията на Чомски и командата grep, която всеки програмист ползва всеки ден.
Илюзията за „разбиращата" машина
В ежедневието ни компютрите изглеждат интелигентни. Те превеждат текстове, разпознават глас, отговарят на въпроси. Създава се усещането, че машините „разбират" езика по начин, подобен на човека.
Това усещане обаче е подвеждащо. Зад всяко действие на компютъра стои не разбиране в човешкия смисъл, а строго формална обработка на символи. За да разберем как работи това, трябва да се запознаем с понятието формален език — едно от фундаменталните понятия в математиката и теоретичната информатика. А за да оценим истинската му дълбочина, трябва да се върнем повече от триста години назад.
Корените: от Лайбниц до Тюринг
Идеята за формален език не е съвременна. Още през XVII век немският философ и математик Готфрид Вилхелм Лайбниц (1646–1716) мечтае за нещо, което той нарича characteristica universalis — универсален символен език, чрез който всяка мисъл може да бъде записана еднозначно и проверена чисто механично. Лайбниц вярва, че споровете между хора могат да се решават не чрез реторика, а чрез изчисление.
Тази визия е прекалено амбициозна за своето време, но тя посява семето на една идея: езикът може да бъде формализиран — превърнат в система от символи и правила, независими от значение, контекст или интуиция.
Две столетия по-късно германският математик Готлоб Фреге (1848–1925) прави решителна стъпка. С Begriffsschrift (1879) — буквално „Писмо на понятията" — той създава първата модерна формална система на логиката. Нотацията му е тромава и визуално странна, но идеята е революционна: логическите разсъждения могат да се записват с абсолютна прецизност, без никаква двусмисленост.
Но истинският пробив идва през 1936 г. Английският математик Алън Тюринг (1912–1954), едва на 24 години, публикува статията On Computable Numbers, with an Application to the Entscheidungsproblem. Контекстът е следният: великият Давид Хилберт поставя въпроса дали съществува механична процедура, която може да определи за всяко математическо твърдение дали е доказуемо. Тюринг се заема да отговори — и за целта измисля нещо, което ще промени света завинаги.
Но Тюринг доказва и нещо не по-малко важно: съществуват проблеми, които никоя такава машина не може да реши — добре дефинирани въпроси, на които принципно не може да се отговори чрез алгоритъм. Това ограничение не е технологично — то е математически факт.
От символи към език: основната идея
Какво е формален език? Нека започнем от нещо елементарно — азбука.
Да вземем азбука от два символа: Σ = {0, 1}. От тях можем да строим низове: 0, 1, 01, 101, 1100 и т.н. Множеството от всички такива низове (включително празния) се означава Σ*.
Сега идва съществената стъпка: избираме правило, което определя кои низове са „разрешени". Например: „Разрешени са всички низове с четен брой единици." Тогава „11" и „1010" са допустими, а „111" — не. Полученото множество от допустими низове е именно формалният език.
Йерархията на Чомски: картата на езиковата сложност
През 1956 г. Ноам Чомски — тогава млад лингвист от MIT, роден на 7 декември 1928 г. — публикува статия, с която дава решителен тласък на теорията на формалните езици. Воден от конкретен лингвистичен въпрос (как формализираме „граматическа правилност"?), той изгражда йерархия от четири типа граматики, подредени по нарастваща мощност. Тази класификация — Йерархията на Чомски — се оказва основополагаща не само за лингвистиката, но и за цялата теоретична информатика.
| Тип | Граматика | Автомат | Приложение |
|---|---|---|---|
| 3 | Регулярна | Краен автомат | Регулярни изрази, валидация |
| 2 | Безконтекстна | Стеков автомат | Синтаксис на програмни езици |
| 1 | Контекстно-зависима | Линейно огр. автомат | Сложни езикови явления |
| 0 | Неограничена | Машина на Тюринг | Всичко изчислимо |
Тип 3 — Регулярни граматики. Разпознават прости шаблони: „всички низове, завършващи с 01" или „всички думи с поне три поредни букви а". Днес ги срещаме навсякъде под формата на регулярни изрази (regular expressions).
Тип 2 — Безконтекстни граматики. Описват вложени структури — правилно отворени и затворени скоби, йерархични конструкции. Синтаксисът на почти всеки програмен език (Python, Java, C++) се описва с безконтекстна граматика.
Тип 0 — Неограничени граматики. Пораждат точно онези езици, разпознавани от машина на Тюринг — всичко принципно изчислимо.
Клини и регулярните изрази: от невронни мрежи до grep
Историята на регулярните изрази започва по неочакван начин — не от компютрите, а от мозъка. През 1943 г. неврофизиологът Уорън Маккълък и логикът Уолтър Питс публикуват първия математически модел на изкуствен неврон.
Осем години по-късно американският математик Стивън Коул Клини (1909–1994) — ученик на Алонзо Чърч в Принстън — пише изследователски меморандум за корпорацията RAND. Клини се пита: какъв тип шаблони може да разпознае мрежа от изкуствени неврони? За да отговори, той абстрахира невронните мрежи като крайни автомати и разработва нотация за описание на езиците, които те разпознават. Той въвежда три операции: обединение (A + B), конкатенация (A ◦ B) и итерация (A*) — последната днес е известна като звездата на Клини.
Регулярните изрази остават академична абстракция, докато Кен Томпсън — един от създателите на UNIX — не ги имплементира през 1968 г. в текстовия редактор QED. По-късно ги вгражда в редактора ed, откъдето се ражда легендарната команда grep (от ed-командата g/re/p — „Global search for Regular Expression and Print"). Така теоретична конструкция, родена от анализа на невронни мрежи, се превръща в ежедневен инструмент на програмисти по целия свят.
Програмирането като формален език
Най-очевидният пример за формален език в действие е всеки програмен език. Разгледайте следното:
За човек втората версия е очевидна — пропуснат е един символ, смисълът е напълно ясен. За компютъра обаче това е невалиден израз, който не принадлежи на езика. Той не „разбира", че сме пропуснали символ. Просто отказва.
Компилаторите работят на базата на йерархията на Чомски в тандем: лексическият анализ разбива кода на токени чрез регулярни изрази (тип 3), а синтактичният анализ проверява дали токените образуват валидна програма чрез безконтекстна граматика (тип 2). Така всеки път, когато натиснете „Run", двете най-ниски нива на йерархията работят заедно.
Автоматите: абстрактните машини, които разпознават
Краен автомат чете символите от входа един по един, преминава през фиксиран брой вътрешни „състояния" и накрая решава дали входът е валиден. Той може да разпознае например всички думи, завършващи с „01" — без да „разбира" думата. Концепцията е формализирана от Майкъл Рабин и Дана Скот в статията Finite Automata and Their Decision Problems (1959), за която двамата получават наградата на Тюринг през 1976 г.
Стеков автомат е краен автомат с допълнителна памет — стек (памет от тип LIFO — последен влязъл, пръв излязъл). Това му позволява да разпознава вложени структури: ((())) е валидно, а (() — не.
Машина на Тюринг получава произволен достъп до памет — безкрайна лента, по която може да се движи и в двете посоки. Тя е теоретичният таван на изчислителната мощност.
Реални приложения навсякъде около нас
Валидация на форми. Правилата за пароли (минимална дължина, задължителен специален символ) са формални условия, проверявани чрез регулярни изрази. Дали имейл адресът ви е валиден — също.
Уеб технологии. XML е строг формален език: един неправилно затворен таг прави документа невалиден. HTML също има формален синтаксис, но браузърите прилагат механизми за възстановяване при грешки.
Биоинформатика. ДНК последователностите (с азбука {A, T, G, C}) се моделират като формални езици. Учените използват граматики и автомати за анализ на генетични секвенции и протеинови структури.
Мрежови протоколи. HTTP, TCP и другите протоколи следват строго дефинирани формални граматики. Всяко отклонение от структурата се отхвърля автоматично.
Защо компютрите не могат да разбират като хората?
Основната причина е, че формалната обработка на символи — колкото и сложна да е — не е семантика. Компютърът няма съзнание, интуиция, опит или контекст. За него съществуват само символи и правила за тяхното подреждане.
Това, което изглежда като разбиране при съвременните езикови модели, е резултат от изключително сложна, но все пак статистическа обработка: моделът е научил закономерности от огромни количества текст и генерира отговори, които са вероятни — не осмислени в човешкия смисъл.
Хронология
Запишете урок
Индивидуални и групови онлайн уроци по математика за цялата страна
- ›НВО по математика след 7 клас
- ›НВО по математика след 10 клас
- ›Кандидатстудентски изпити по математика
- ›Софийски университет „Св. Климент Охридски“
- ›УАСГ – Университет по архитектура, строителство и геодезия
- ›Технически университет – София и др.
- ›Прием в университети в чужбина (ISEE, SAT, A-Level и др.)
- ›Усвояване на текущия учебен материал (всички класове)
- ›Студенти по всички математически дисциплини:
Математически анализ, Линейна алгебра, Аналитична геометрия, Диференциални уравнения, Теория на вероятностите, Статистика и др.
Харесва ли ви съдържанието?
Ако тази статия ви е харесала, можете да подкрепите създаването на нови безплатни материали.
Коментари
Публикуване на коментар