Формални езици

Формалният език е нещо като обобщение на понятието език, с което сме свикнали от ежедневието.

Основни понятия

Като начало можем да си представим формалния език като обикновен език, например български. От какво се състои такъв език? Състои се от думи, които след това свързваме в изречения. Изреченията няма да ни интересуват, ще се занимаваме само с думите. От какво се състоят думите? От буквите на азбуката. Затова ще започнем с азбуката.

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

Дума, или още низ, наричаме крайна редица от символи от някаква азбука Σ. Ако например имаме азбуката Σ= {a,b,c,d,e,…, z}, то дума е например редицата „ahoj“ или „dobrman“, но не и „café“ (нямаме буквата „é“), „Ivan“ (нямаме буквата „I“) или „dobry den“ (нямаме интервал). Дължина на думата наричаме броя на символите, от които се състои думата.

Конкатенация на думи: ако имаме две думи a = a₁a₂… a_n и b = b₁b₂… b_m, то чрез конкатенация на думите се получава думата ab = a₁a₂… a_nb₁b₂… b_m. Пример: чрез конкатенация на думите „ahoj“ и „dobrman“ се получава думата „ahojdobrman“. Конкатенацията означаваме или с кръгче, т.е. a ∘ b, или изобщо не я означаваме и просто записваме думите една след друга, без специален символ за конкатенация.

Празната дума означаваме с ε и с нея означаваме думата, която има дължина нула. Ако конкатенираме думата a = a₁… a_n с празната дума ε, получаваме отново думата a. Т.е. a ∘ ε = a.

Затваряне на азбуката Σ е множеството от всички думи, които можем да съставим от азбуката Σ, включително празната дума. Затварянето означаваме с Σ^∗. Ако имаме двоичната азбука Σ= {0, 1}, то

$Σ^{*} = {ε, 0, 1, 00, 01, 10, 11, 000, 001, \dots}$

Понякога използваме и положително затваряне на азбуката, което е отново множеството от всички думи, които можем да съставим от азбуката, с изключение на празната дума. Положителното затваряне означаваме с Σ⁺ и е в сила Σ⁺ = Σ^∗ ∖ {ε}.

Примери за азбуки

Да се върнем към примера с българския език. Всяка българска дума се намира в затварянето на азбуката, която съдържа малките и главните букви (и може би още тире „-“). Ако към тази азбука добавим още интервал и препинателните знаци (запетая, точка, удивителен знак, въпросителен знак, …), чрез затварянето получаваме всички изречения, които можем да съставим на български. Разбира се, част от това затваряне са и изречения от рода на „сдфлсф касдф кагрйевщжчъюяшк кф фкйбсйбгвбадфгса!!!:??: ::!?:?:сдф“, които обаче пак имат повече смисъл от някои коментари в интернет.
Ако азбуката ни съдържа всички цифри Σ= {0, 1, …, 9}, то в затварянето ще бъдат всички естествени числа — и още някои допълнително. Там ще има и числа, които започват с нула, например 00054, самата нула, а освен това ще има и празната дума, която, разбира се, не е никакво число.
Азбуката трябва да е непразна, така че най-малката азбука има поне един символ. Например за азбуката Σ= {!} бихме получили затваряне Σ^∗ = {ε, !, !!, !!!, !!!!, …}, т.е. множество от думи, като за всяко n ∈ ℕ₀ в затварянето има дума с n удивителни знака и няма друга дума.
Нека Σ= {qw,c}. Това е много странна азбука, защото съдържа думата qw. Такъв запис обикновено не се използва, защото е объркващ и чудат, но можем да си го представим така, че залепваме буквите „q“ и „w“ една за друга и те образуват един знак. Тогава можем да гледаме на „qw“ като на символа „qw“. Ако от този символ образуваме думата „qwcqw“, тази дума ще има дължина три — ще се състои от символите „qw“, „c“ и „qw“. Не се срещаме често с подобни азбуки, но има ситуации, в които ни трябват такива символи, съставени от няколко символа.

Формален език

(Формален) език над азбуката Σ е произволно подмножество на Σ^∗. За език L над азбуката Σ следователно е в сила L ⊆ Σ^∗. Примери за езици:

В предишната част определихме азбуката от цифри Σ= {0, 1, …, 9}. Затварянето са всички думи, съставени само от цифри. Ако добавим правилото, че думата не може да започва с нула и не може да е празна, получаваме множеството на естествените числа ℕ. Понеже ℕ ⊆ Σ^∗, множеството ℕ е език над азбуката Σ.
Към предишното множество от цифри можем да добавим и знака минус „-“, така че Σ= {0, 1, …, 9, −}. Затварянето са всички думи, които се състоят от цифри или от знака минус. Това обаче означава, че в затварянето има и думи като „12-84-“, „1-5-8“ или „-“. Езика на целите числа ℤ получаваме, като добавим три правила:
- Знакът минус изобщо не се среща в думата или се среща в началото ѝ.
- Първата цифра в думата не може да е нула, освен ако думата е „0“.
- Всяка дума трябва да съдържа поне една цифра.
Това множество описва множеството на целите числа и е подмножество на Σ^∗ — следователно е език над азбуката Σ.
Нека Σ= {0, 1}. Затварянето са всички думи, които се състоят от нули и единици. Език L над тази азбука можем да определим например като множеството на всички думи, които имат точно три единици. Можем да бъдем и по-изобретателни и да кажем, че езикът L е множеството на всички думи, които представляват валиден формат на файл docx (това, което излиза от Word).
Да останем при двоичната азбука Σ= {0, 1}. Всеки низ от знаци (обикновени знаци, които имаш на клавиатурата) може да се преобразува в двоичен вид, т.е. в нули и единици, и обратно, например с помощта на ASCII таблицата (или по-точно — ASCII таблицата преобразува знаците в числа, а числата от десетична в двоична бройна система се преобразуват). Така можем да определим езика на всички думи, които отговарят на валиден имейл, и пак ще е език над двоичната азбука.

Конкатенация на езици: можем да конкатенираме и езици. Определението е подобно на това за декартово произведение на множества. Нека имаме два езика L₁ и L₂. Чрез тяхната конкатенация L₁ ∘ L₂ получаваме нов език, който определяме така:

$L_{1} \circ L_{2} = {w_{1} \circ w_{2} | w_{1} \in L_{1}, w_{2} \in L_{2}}$

Т.е. вземаме всички думи от езика L₁ и ги конкатенираме с всички думи от езика L₂. Пример: нека

$\begin{array}{rcl} L_{1} & = & {0, 1} \\ L_{2} & = & {a, b, a h o j} \end{array}$

Тогава е в сила:

$\begin{array}{rcl} L_{1} \circ L_{2} & = & {0 a, 0 b, 0 a h o j, 1 a, 1 b, 1 a h o j} \\ L_{2} \circ L_{1} & = & {a 0, a 1, b 0, b 1, a h o j 0, a h o j 1} \\ L_{1} \circ L_{1} & = & {00, 01, 10, 11} \end{array}$

Досега за описание на езиците използвахме обикновен език, просто описвахме с думи как трябва да изглежда езикът. Това обаче е много непрактично, затова се въвежда по-формален начин за определяне на език. Първият от тях е граматиката.

« Предишна: Информатика

Следваща: Крайни автомати »