Азбука в информатиката: дефиниция, примери и формални езици

Открийте азбуката в информатиката: ясна дефиниция, примери (двоична, морзова), Клайн-звезда и значението ѝ за формални езици и крайни автомати.

В информатиката азбуката е крайно непразно множество. Елементите на една азбука се наричат букви или символи на азбуката.

По-кратко: азбуката е фиксирана, ограничена по брой колекция от отделни символи, от които се градят по-дълги структури (низове). Размерът на азбуката често се означава с |Σ|, когато използваме общата нотация Σ за азбука. Азбуките могат да бъдат от два, три или повече символа (например {0,1}, {a,b,c}), както и многобройни реални кодировки като ASCII или Unicode — но във формалната теория често разглеждаме крайни множества символи.

Пример за азбука е { - , ⋅ } {\displaystyle \{-,\cdot \}}, която може да се използва за морзовата азбука, или {begin, if, else, for, while}, които могат да бъдат ключовите думи на език за програмиране.

Множеството на естествените числа не е азбука, тъй като не е крайно. Тоест не може да служи като азбука в дефиницията на формални езици, защото азбуката трябва да съдържа крайно (ограничено) число символи.

Низове (думи) и празният низ

Низ (често наричан и дума) е крайна последователност от букви на дадена азбука. Ако Σ е азбука, тогава низ върху Σ е редица от символи от Σ, например 01101 е низ върху {0,1}. Дължината на низа w се означава |w| (например |01101| = 5). Операцията за свързване (конкатенация) на два низа x и y се пише xy и означава редицата, получена от поставяне на y след x.

Празният низ е низът, който не съдържа букви (често се записва като λ {\displaystyle \lambda } ). Празният низ е низ над всяка азбука и играе ролята на неутрален елемент за конкатенация (wλ = λw = w за всеки низ w).

Нотация Σ и звездата на Клайн

Ако имаме азбука, наречена Σ {\displaystyle \Sigma } . Тогава записваме множеството от всички низове, които могат да бъдат създадени от Σ {\displaystyle \Sigma }, като Σ ∗ {\displaystyle \Sigma ^{*}} . Това се нарича звезда на Клайн (или затваряне на Клайн) на Σ {\displaystyle \Sigma } . Наречена е на името на математика Стивън Коул Клайн.

Звездата на Клайн съдържа всички възможни низове от Σ с всякаква дължина, включително празния низ. Съвършено ясно е, че ако Σ е непразно крайно множество, то Σ* е безкрайно (винаги има низове с произволно голяма дължина). Понякога използваме и Σ+ (позитивна звезда), която означава всички низове с дължина най-малко 1 (тоест Σ+ = ΣΣ*).

Звездата на Клайн на двоичната азбука е { λ , 0 , 1 , 00 , 01 , 10 , 11 , 000 , 001 , ... . } {\displaystyle \{\lambda ,0,1,00,01,10,11,000,001,...\}} . Трите точки след 001 показват, че не можем да напишем изцяло звездата на Клайн на азбуката, защото тя е безкрайно множество.

Езици и операции върху езици

Формален език над азбука Σ е просто подмножество L ⊆ Σ*. Тоест езикът е набор от низове. Примери:

• Езикът на всички двоични низове с четен брой единици.
• Езикът {a^n b^n | n ≥ 0} (низове от n повтарящи се a, последвани от n b), който е контекстно-свободен.
• Езикът на всички низове, които съдържат подниза "while".

Честите операции между езици включват съединение (L1 ∪ L2), конкатенация (L1L2 = {xy | x ∈ L1, y ∈ L2}), и Клайнова звезда (L* = ∪_{i≥0} L^i, където L^0 = {λ}). Много класове езици са затворени под тези операции (например регулярните езици са затворени под съединение, конкатенация и звездата).

Класове езици и автомати

Азбуките са основата за теорията на формалните езици и автоматите. Някои важни класове езици:

• Регулярни езици — описват се от регулярни изрази и се разпознават от крайни автомати (детерминирани и недетерминирани).
• Контекстно-свободни езици — описват се от контекстно-свободни граматики и се разпознават от стекови автомати; пример: езиците на добре балансирани скоби.
• Контекстно-зависими и рекурсивно изброими езици — по-сложни класове в йерархията на Чомски, свързани с мощността на различни модели на изчисление (например линейно ограничени автомати или Тюрингова машина).

Практическо приложение: изборът на азбука влияе върху представянето на данни и кода (например двоични битови низове в компютърната памет; азбука от ключови думи и оператори в езиците за програмиране). В теорията на изчислимостта и сложността изучаваме как свойствата на езици над дадена азбука (например дали езикът е празен, дали съдържа безкрайно много низове, дали е разпознаваем) се свързват със способността на алгоритмите да ги решават.

Допълнителни бележки

• Ако Σ е крайна азбука от k символа, то за всяка фиксирана дължина n има точно k^n низа от дължина n над Σ. Така Σ* е броимо (изброимо) безкрайно множество.
• Понякога в практиката работим с "азбуки" от по-големи символни множества — напр. байтове (256 стойности) или Unicode кодови точки — но при формалните дефиниции все още разглеждаме крайни множества.
• Поднизи: prefix (начален фрагмент), suffix (краен фрагмент) и substring (подниз). Тези понятия са важни в алгоритмите за обработка на низове и при анализ на езици.

Азбуките са важни, защото се използват при изучаването на формални езици, крайни автомати и много трудни въпроси в информатиката за това какво може да се изчисли и какво не.

Въпроси и отговори

В: Какво представлява азбуката?

В: Може ли множеството на естествените числа да се счита за азбука?

В: Коя е най-често използваната азбука в информатиката?

В: Какво означава да се направи низ от азбука?

В: Какво означава звезда на Клайн?

Въпрос: Как можем да представим звездата на Клайн за двоичния алфбет?

Въпрос: Защо азбуките са важни в информатиката?

Търсене по буква