Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


Алфавит, слово, язык в программировании

Алфавит, слово, язык в программировании


Рассмотрим самое простое понятие теории языков — понятие алфавита.


Алфавит — это произвольное непустое конечное множество [math]V=\{a_1,\ldots,a_n\}[/math], элементы которого называют буквами или символами.


Обычно задают определенную нумерацию алфавита (как, скажем, для русского алфавита: "а" — первая буква, "б" — вторая и т.д. до 33-й — "я"). Впредь договоримся, фиксируя алфавит, записывать его буквы в порядке их номеров.


Определение 7.1. Словом или цепочкой в алфавите [math]V[/math] называют произвольный кортеж из множества [math]V^k[/math] (k-й декартовой степени алфавита [math]V[/math]) для различных [math]k=0,1,2,\ldots[/math]


Например, если [math]V=\{a,b,c\}[/math], то [math](a),(b),(c),(a,b),(a,b,c),(c,b,a,a,c)[/math] и т.д. есть слова в [math]V[/math].


При [math]k=0[/math] получаем пустой кортеж, называемый в данном контексте пустым словом или пустой цепочкой и обозначаемый [math]\lambda[/math]. Множество всех слов в алфавите [math]V[/math] обозначают [math]V^{\ast}[/math], а множество всех непустых слов в [math]V[/math] — как [math]V^{+}[/math]. Слова, ради удобства чтения и простоты записи, будем записывать без скобок и запятых. Так, для записанных выше слов получим:


[math]a,\quad b,\quad c,\quad ab,\quad abc,\quad cbaac\,.[/math]

Такая запись слова согласуется с его интуитивным пониманием как цепочки следующих друг за другом символов. Тогда пустое слово — это слово, не имеющее символов, "пустой лист бумаги", на котором еще ничего не написано.


По определению, длина слова [math]w[/math] — число компонент кортежа, т.е. если [math]w\in V^{\tau}[/math], то длина слова [math]w[/math] равна [math]\tau[/math]. Длину слова [math]w[/math] договоримся обозначать [math]|w|[/math]. Ясно, что для пустого слова [math]|\lambda|=0[/math]. Длину слова тем самым можно понимать как число составляющих это слово букв.


Докажем, что множество [math]V^{\ast}[/math] счетно. Для этого достаточно построить какую-либо нумерацию этого множества. Рассмотрим здесь нумерацию, называемую лексикографической.


В данной нумерации пустому слову присваивается номер 0, а буквам [math]a_1,\ldots,a_n[/math] алфавита [math]V[/math] — номера [math]1,\ldots,n[/math] соответственно. Если слово [math]x[/math] имеет лексикографический номер [math]l_x[/math], то слову [math]xa_i[/math] присваивается номер [math]nl_x+i[/math]. Отсюда следует, что лексикографический номер слова [math]a_{i_1},a_{i_2},\ldots,a_{i_k}[/math] будет равен


[math]n^{k-1}i_1+n^{k-2}i_2+\ldots+i_k\,.[/math]

Заметим, что последняя сумма напоминает запись числа в системе счисления по модулю [math]n[/math] (мощности алфавита) с тем лишь различием, что используется цифра [math]n[/math], но не допускается цифра 0. Итак, по любому слову в алфавите [math]V[/math] однозначно вычисляется его лексикографический номер. Обратно, любое натуральное число однозначно раскладывается по степеням [math]n[/math] указанным выше образом.


Действительно, если дано число [math]N[/math], то при [math]0\leqslant N\leqslant n[/math] оно служит номером пустого слова [math](N=0)[/math] или некоторой буквы алфавита. Иначе представим [math]N[/math] в виде [math]N=k_1n+r_0[/math], где [math]1\leqslant r_0\leqslant n[/math].


Если [math]k_1\leqslant n[/math], то [math]N[/math] есть номер слова [math]a_{k_1}a_{r_0}[/math]. Иначе раскладываем [math]k_1[/math] в виде


[math]k_1=k_2n+r_1[/math], где [math]1\leqslant r_1\leqslant n[/math]. Тогда [math]N=k_2n^2+r_1n+r_0[/math].

С числом [math]k_2[/math] поступаем точно так же, как и с [math]k_1[/math]. После конечного числа шагов получим разложение числа [math]N[/math] в виде


[math]N=n^m\cdot r_m+n^{m-1}\cdot r_{m-1}+\ldots+n\cdot r_1+r_0,[/math]

где каждое число [math]r_i~(0\leqslant i\leqslant m)[/math] находится в диапазоне от 1 до [math]n[/math]. По полученному разложению [math]N[/math] однозначно восстанавливается слово в [math]V[/math], имеющее номер [math]N:[/math]


[math]a_{r_m}a_{r_{m-1}}\ldots a_{r_1}a_{r_0}.[/math]

Пример 7.1. Вычислим номер слова [math]cbaac[/math] в алфавите [math]\{a,b,c\}[/math]. Имеем


[math]3^4\cdot3+3^3\cdot2+3^2\cdot1+3^1\cdot1+3=279.[/math]

Решим обратную задачу, найдя слово в данном трехбуквенном алфавите, имеющее номер 321. Согласно приведенному выше алгоритму, получим


[math]\begin{aligned}\begin{aligned}321&= 106\cdot3+3=(35\cdot3+1)\cdot3+3= (11\cdot3+ 2)\cdot3^2+1\cdot3+3\cdot3^0=\\[2pt] &=(3\cdot3 + 2) \cdot 3^3+ 2\cdot 3^2 + 1\cdot 3 + 3\cdot 3^0 = 3\cdot 3^4 + 2\cdot 3^3 + 2\cdot 3^2 + 1\cdot 3 + 3.\end{aligned}\end{aligned}[/math]

Следовательно, искомое слово есть [math]cbbac[/math].




Лексикографическая нумерация напоминает способ упорядочения слов в словарях: однобуквенные слова следуют в порядке номеров букв в алфавите, среди двух двухбуквенных слов меньший номер имеет слово, начинающееся буквой с меньшим номером, и т.д. Но полного совпадения нет, так как в словаре слова группируются по начальной букве, а не по длине.


Нам будет удобно в дальнейшем использовать следующую запись непустого слова [math]x[/math] в алфавите [math]V[/math] по буквам:


[math]x=x(1)x(2)\ldots x(k)[/math], где [math]x(i),~1\leqslant i\leqslant k[/math], — i-я буква слова [math]x[/math].

Определение 7.2. Языком в алфавите [math]V[/math] называется произвольное подмножество множества [math]V^{\ast}[/math].


Множество всех языков в алфавите [math]V[/math], т.е. множество [math]2^{V^{\ast}}[/math], есть булеан счетного множества, и, следовательно, оно в силу теоремы 1.15 Кантора имеет мощность континуума.


Наша следующая задача — определить на множестве [math]2^{V^{\ast}}[/math] всех языков в произвольном (но фиксированном!) алфавите [math]V[/math] алгебраическую структуру. На множестве [math]2^{V^{\ast}}[/math] можно определять различные операции. Прежде всего языки — это множества, следовательно, над ними можно производить все те же операции, что и над множествами: объединение, пересечение, разность, дополнение и т.п. Универсальное множество в данном случае есть множество слов [math]V^{\ast}[/math], которое называют универсальным языком.


Кроме перечисленных теоретико-множественных операций можно рассматривать и специальные операции над языками.


Прежде чем обратиться к этим операциям, определим операцию соединения (или конкатенации) слов. Соединением слов [math]x=x(1)x(2)\ldots x(k)[/math] и [math]y=y(1)y(2)\ldots y(m)[/math] называют слово


[math]xy= x(1)x(2)\ldots x(k) y(1)y(2)\ldots y(m).[/math]

По определению, считаем [math]x\lambda=\lambda x=x[/math] для любого [math]x[/math]. Соединение иногда обозначают точкой [math](\,\cdot\,)[/math].


Неформально соединение [math]xy[/math] получается приписыванием слова [math]y[/math] справа к слову [math]x[/math]. Таким образом, для любых двух слов [math]x\in V^k[/math] и [math]y\in V^m[/math] конкатенация [math]xy\in V^{k+m}\,(k,m\geqslant0)[/math]. Следовательно, [math]|xy|=|x|+|y|[/math].


Из определения также следует, что соединение слов ассоциативно, т.е. для произвольных трех слов [math]x,y,z[/math] имеет место [math]x(yz)=(xy)z[/math], и поэтому — с учетом написанного выше свойства пустого слова — множество [math]V^{\ast}[/math] всех слов в алфавите [math]V[/math] с операцией соединения образует моноид [math](V^{\ast},\cdot,\lambda)[/math]. Единица моноида — пустое слово. Этот моноид есть не что иное, как свободный моноид, порожденный алфавитом [math]V[/math] (см. пример 2.7). Для него используют то же обозначение, что и для самого множества всех слов в алфавите [math]V[/math], то есть [math]V^{\ast}[/math].




Вхождения одного слова в другое


На основе понятия соединения слов определим понятие вхождения одного слова в другое.


Определение 7.3. Вхождение слова [math]x\in V^{\ast}[/math] в слово [math]y\in V^{\ast}[/math] — это упорядоченная тройка слов [math](u,x,v)[/math], такая, что [math]y=uxv[/math].


При этом слово [math]u[/math] называют левым, а слово [math]{v}[/math] — правым крылом указанного вхождения. Слово [math]x[/math] называют основой вхождения.


Говорят, что слово [math]x[/math] входит в слово [math]y[/math], если существует вхождение [math]x[/math] в [math]y[/math]. При этом также слово (цепочку) [math]x[/math] называют подсловом (или подцепочкой) слова (цепочки) [math]y[/math]. Подцепочку [math]x[/math] цепочки [math]y[/math] называют началом (или префиксом) цепочки [math]y[/math], если [math]y=xz[/math] для некоторой непустой цепочки [math]z[/math]; если же для некоторой непустой цепочки [math]z[/math] имеет место [math]y=zx[/math], то цепочку [math]x[/math] называют концом (или постфиксом) цепочки [math]y[/math].


Заметим, что каждое слово входит в себя само и пустое слово входит в любое слово.


Например, слова "цикл" и "циклоп" входят в слово "энциклопедия". Соответствующие вхождения записывают следующим образом:


(эн, цикл, опедия), (эн, циклоп, едия)

Может существовать несколько разных вхождений одного и того же слова [math]x[/math] в некоторое слово [math]y[/math]. Так, слово "абра" дважды входит в слово "абракадабра". Число вхождений пустого слова в данное слово [math]p[/math] на единицу больше длины слова [math]p[/math]. Среди всех вхождений слова [math]x[/math] в слово [math]y[/math] вхождение с наименьшей длиной левого крыла называют первым или главным вхождением [math]x[/math] в слово [math]y[/math].


Так, вхождение ([math]\lambda[/math], абра, кадабра) есть первое вхождение слова "абра" в слово "абракадабра".


Определение 7.4. Говорят, что вхождения [math](u,x,v)[/math] и [math](s,z,t)[/math] слов [math]x[/math] и [math]z[/math] в одно и то же слово [math]y[/math] не пересекаются, если существуют такие (может быть, и пустые) слова [math]p[/math] и [math]q[/math], что [math]y=uxpzt[/math] (и тогда [math]v=pzt[/math], а [math]s=uxp[/math]) или [math]y=szqxv[/math] (и тогда [math]u=szq[/math], а [math]t=qxv[/math]) (рис. 7.1). В противном случае говорят, что указанные вхождения пересекаются.


Пересекающиеся и непересекающиеся вхождения слов в одно и то же слово

Так, вхождения слов "цикл" и "циклоп" в слово "энциклопедия" пересекаются, а два разных вхождения слова "абра" в слово "абракадабра" не пересекаются. Мы иногда будем использовать обозначение [math]x\sqsubseteq y[/math] для утверждения "слово [math]x[/math] входит в слово [math]y[/math]". Можно доказать, что [math]\sqsubseteq[/math]. — отношение порядка.


Определив таким образом операцию соединения слов, введем теперь операцию с таким же названием, но уже для языков. Перед этим обратим внимание на то, что всякий раз, говоря о языках и операциях над ними, мы полагаем фиксированным какой-то алфавит [math]V[/math]. Он не всегда явно упоминается, но нужно четко усвоить, что нельзя говорить просто о слове, просто о языке, но всегда — о слове или языке в том или ином алфавите.


Определение 7.5. Соединением (конкатенацией) языков [math]L_1[/math] и [math]L_2[/math] называют язык [math]L_1L_2[/math], состоящий из всех возможных соединений слов [math]xy[/math], в которых слово [math]x[/math] принадлежит первому, а слово [math]y[/math] — второму языку, т.е.


[math]L_1L_2=\bigl\{xy\colon\, x\in L_1,~y\in L_2\bigr\}.[/math]

Соединение конечных языков легко вычислить.


Пример 7.2. Если [math]V=\{a,b,c\},~L_1=\{ab,bcc,cab\},~ L_2=\{ca,bcc\}[/math], то


[math]L_1L_2=\bigl\{abca,\, abbcc,\, bccca,\, bccbcc,\, cabca,\, cabbcc\bigr\},[/math] а

[math]L_2L_1=\bigl\{caab,\, cabcc,\, cacab,\, bccab,\, bccbcc,\, bcccab\bigr\}.[/math]

Вычисление конкатенации языков в конечном случае очень похоже на умножение (раскрытие скобок) в обычной школьной алгебре. Можно былб бы формально написать так:


[math](ab+bcc+cab)(ca+bcc)= abca+ abbcc+ bccca+ bccbcc+ cabca+ cabbcc\,.[/math]

В данном случае плюс [math](+)[/math] — это только соединительный знак, используемый вместо запятой. Позже мы увидим, что подобным чисто формальным записям может быть придан строгий алгебраический смысл.




Итерация языка и возведение его в степень


Соединение языков не коммутативно, и, как показывает только что разобранный пример, пересечение [math]L_1L_2\cap L_2L_1[/math] в общем случае не пусто. В нашем примере оно содержит одну цепочку [math]bccbcc[/math].


Операция соединения языков позволяет определить операцию возведения языка в произвольную натуральную степень. А именно, по определению, [math]L^0=\{\lambda\}[/math] для любого [math]L\subseteq V^{\ast}[/math], а [math]L^n=L^{n-1}L[/math] при [math]n>0[/math].


Итерацией языка [math]L[/math] называют объединение всех его степеней:


[math]L^{\ast}=\bigcup\limits_{n=0}^{\infty}L^n.[/math]

Рассматривая объединение всех степеней языка [math]L[/math], начиная с первой, получим позитивную итерацию


[math]L^{+}=\bigcup\limits_{n=1}^{\infty}L^n.[/math]



Основное алгебраическое свойство множества всех языков


Сформулируем основное алгебраическое свойство множества всех языков в алфавите [math]V[/math].


Теорема 7.1. Алгебра [math]\mathcal{L}(V)=(2^{V^{\ast}},\cup,\cdot, \varnothing, \{\lambda\})[/math] есть замкнутое полукольцо.


Проверка аксиом полукольца сводится к доказательству:


1) того, что по операции объединения множество всех языков образует коммутативный и идемпотентный моноид (с пустым множеством в качестве нейтрального элемента (нуль полукольца)); это тривиально ввиду известных свойств операции объединения множеств;


2) того, что по операции конкатенации множество языков образует моноид (с языком [math]\{\lambda\}[/math], состоящим из одного пустого слова, в качестве нейтрального элемента (единицы полукольца)); для этого достаточно доказать, что операция соединения языков ассоциативна, а также доказать для любого языка [math]L[/math] тождество [math]\{\lambda\}L=L\{\lambda\}=L[/math], что вытекает из ассоциативности операции соединения слов и из тождества [math]\lambda x=x\lambda=x[/math] для любого слова [math]x[/math];


3) следующих тождеств:

[math]L_1(L_2\cup L_3)=L_1L_2\cup L_1L_3,\qquad (L_1\cup L_2)L_3=L_1L_3\cup L_2L_3[/math]

(эти тождества определяют свойство дистрибутивности операции соединения относительно объединения).

Докажем первое из этих тождеств. Пусть слово [math]x[/math] принадлежит его левой части, т.е. языку [math]L_1(L_2\cup L_3)[/math]. Тогда, согласно определению соединения языков, это слово может быть представлено в виде [math]x=yz[/math], где [math]y\in L_1[/math], а [math]z\in L_2\cup L_3[/math], то есть [math]z\in L_2[/math] или [math]z\in L_3[/math]. Если [math]z\in L_2[/math], то [math]yz\in L_1L_2[/math], а если [math]z\in L_3[/math], то [math]yz\in L_1L_3[/math], то есть [math]x=yz\in L_1L_2\cup L_1L_3[/math]. Пусть теперь [math]x\in L_1L_2\cup L_1L_3[/math]. Тогда [math]x=yz[/math], где [math]y\in L_1[/math], a [math]z\in L_2[/math] или [math]z\in L_3[/math], то есть [math]x\in L_1(L_2\cup L_3)[/math], что и завершает доказательство первого тождества. Второе доказывается аналогично.


Напомним, что в полукольце [math]\mathcal{S}=(S,+,\cdot,0,1)[/math] отношение порядка вводится следующим образом: для любых [math]x,y\in S[/math] по определению полагают [math]x\leqslant y[/math] тогда и только тогда, когда [math]x+y=y[/math]. Так как в полукольце всех языков в алфавите [math]V[/math] операция сложения — это операция объединения множеств, то в данном случае отношение порядка [math]\leqslant[/math] есть не что иное, как теоретико-множественное включение [math]\subseteq[/math] (действительно, включение [math]L\subseteq K[/math] равносильно тому, что [math]L\cup K=K[/math]). Тогда замкнутость полукольца [math]\mathcal{L}(V)[/math] следует из существования объединения любого семейства множеств (в частности, бесконечной последовательности множеств), служащего точной верхней гранью этого семейства (относительно теоретико-множественного включения), а также из следующих тождеств (для любого языка [math]L[/math] и любого семейства языков [math]P_i,~i\in I[/math]):


[math]L\Bigl(\,\bigcup\limits_{i\in I}P_i\,\Bigr)= \bigcup\limits_{i\in I}(LP_i),\qquad \Bigl(\,\bigcup\limits_{i\in I}P_i\,\Bigr)L=\bigcup\limits_{i\in I}P_iL\,,[/math]
(7.1)

что гарантирует выполнение непрерывности операции умножения данного полукольца, т.е. непрерывности операции соединения. Эти тождества доказываются точно так же, как тождества обычной дистрибутивности.


Рассмотрим, например, доказательство второго тождества из (7.1), используя, как и выше, метод двух включений. Если


[math]x\in \Bigl(\,\bigcup\limits_{i\in I}P_i\,\Bigr)L[/math], то [math]x=yz[/math], где [math]y\in \bigcup\limits_{i\in I}P_i[/math], а [math]z\in L[/math].

Согласно определению объединения семейства множеств, найдется такое [math]i\in I[/math], что [math]y\in P_i[/math], и тогда [math]yz=x\in P_iL[/math], то есть [math]\textstyle{\mathop{x\in \bigcup\limits_{i\in I}P_iL}\limits^{\phantom{A}^{.}}}[/math]. Обратное включение доказываем так: из [math]\textstyle{\mathop{x\in \bigcup\limits_{i\in I}P_iL}\limits^{\phantom{A}^{.}}}[/math] следует, что для некоторого [math]i\in I[/math] имеется [math]x\in P_iL[/math], то есть [math]x=yz[/math], где [math]y\in P_i[/math], a [math]z\in L[/math], откуда [math]\textstyle{\mathop{y\in \bigcup\limits_{i\in I}P_i}\limits^{\phantom{A}^{.}}}[/math], и, следовательно, [math]\textstyle{\mathop{yz=x\in \Bigl(\bigcup\limits_{i\in I}P_i\Bigr)L}\limits^{\phantom{A}^{.}}}[/math].


Следствие 7.1. Для любого языка [math]L[/math] верно тождество [math]L^{+}=L^{\ast}L=LL^{\ast}[/math].


Вычислим соединение [math]\textstyle{LL^{\ast}\colon\, LL^{\ast}=L\bigcup\limits_{n=0}^{\infty} L^n}[/math]. Применяя первое из тождеств (7.1), получим


[math]L\bigcup\limits_{n=0}^{\infty}L^n=\bigcup\limits_{n=0}^{\infty}LL^n= \bigcup\limits_{n=0}^{\infty}L^n[/math], то есть [math]L^{+}=L^{\ast}L[/math].

Тождество [math]L^{+}=LL^{\ast}[/math] доказывается аналогично.


Заметим, что в общем случае нельзя утверждать, что позитивная итерация языка [math]L[/math] получается выбрасыванием из обычной итерации пустого слова. Это верно в том и только в том случае, когда язык [math]L[/math] не содержит пустого слова. Если же [math]\lambda\in L[/math], то [math]L^{+}=L^{\ast}[/math], так как тогда [math]L^{0}=\{\lambda\}\subseteq L[/math].


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved