Полные разделимые языки

بسم الله الرحمن الرحيم

I. Полные разделимые языки

Определение 1. Алфавит — это множество из N букв.

Определение 2. Строка — любая последовательность букв. В том числе бесконечная вправо, влево и в обе стороны. Но по умолчанию конечная.

Определение 3. Язык — любое множество строк.

Определение 4. Слово — элемент языка.

Определение 5. Текст — последовательность слов.

Определение 6. Разделимый язык — язык, у которого не может быть так, чтобы разные ряды слов образовывали одну и ту же строку. То есть каждый текст разбивается на слова единственнейшим образом.

Например, язык {a, ab, bc, c} – неразделимый, ибо a+bc = ab+c.

Для разделимого языка естественно использовать производящие функции. Пусть `w(x)=sum_(n=1)^oo w_nx^n`, где `w_n` – это количество n-буквенных слов в нашем языке. Тогда
`w(x)+w(x)^2+w(x)^3+w(x)^4+w(x)^5+... =(w(x))/(1-w(x))` – это производящая функция для количества n-буквенных текстов.

Определение 7. Полный разделимый язык (ПРЯ) – такой разделимый язык, что любая строка, начинающаяся и заканчивающаяся на слово, является текстом.

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

Определение 8. Максимальный текст — самый длинный текст, являющийся подстрокой данной строки.

В ПРЯ максимальный текст строится единственным образом: находим самое левое и самое правое слово. По определению ПРЯ эти слова вместе со всеми буквами между ними (если они есть) образуют текст.

Определение 9. Антислово — строка, не содержащая слов. Очевидно, что любая подстрока антислова – тоже антислово.

Из всего вышесказанного понятно, что справедлива

Теорема 1. Относительно ПРЯ любая строка единственным образом является одним и только одним из следующих пяти:

1. антислово
2. текст
3. антислово слева + максимальный текст
4. максимальный текст + антислово справа
5. антислово слева + максимальный текст + антислово справа

Приведу пример. Возьмём язык {ab, aab, abb, aaab, aabb, abbb, ...}. Тогда

1. bbbaa – антислово
2. aabababbbaaab – текст aab ab abbb aaab
3. bbbbbbaababbbab – антислово слева bbbbbb + текст aab abbb ab
4. aaaabbabbaabbaaaaa – текст aaaabb abb aabb + антислово справа aaaaa
5. bbababbaaba – антислово слева bb + текст ab abb aab + антислово справа a

II. Приставки и суффиксы

Определение 10. Приставка — строка p такая, что существует слово a такое, что pa — тоже слово. Приставка называется универсальной, если она применима ко всем словам. Элементарная приставка – это приставка, которая не заканчивается на более короткую приставку.

Определение 11. Суффикс — строка s такая, что существует слово a такое, что as — тоже слово. Суффикс называется универсальным, если он применим ко всем словам. Элементарный суффикс – это суффикс, который не начинается на более короткий суффикс.

Теорема 2. Если в каком-то языке все элементарные приставки(суффиксы) универсальны, то тогда универсальны вообще все приставки(суффиксы) и все они являются конкатенацией элементарных. Причём единственным образом.

Легко понять, что конкатенация универсальных приставок снова универсальная приставка. Теперь берём какую-нибудь неэлементарную приставку p. Очевидно, что p = qp₁, где p₁ – элементарная приставка. Получаем, что существует слово w такое, что pw = qp₁w тоже является словом. Так как p₁ универсальна, то p₁w является словом. А значит q – это тоже приставка. Если она элементарна, то теорема доказана, а если неэлементарна, то поступаем с q так же, как с p. В конце концов придем к элементарной.

Аналогично для суффиксов. Единственность очевидна. Теорема доказана.

Определение 12. Правильный язык – язык, в котором все приставки и суффиксы универсальны.

Определение 13. Приставка текста — строка, которая, будучи приставлена слева к тексту, снова образует текст. Короче то же самое, что и просто приставка, но не только для слов, но и для текстов. Аналогично определяется суффикс текста.

III. Производящие функции

Возратимся к теореме 1 и посмотрим, что в ней надо изменить, чтобы можно было воспользоваться производящими функциями. Для этого надо, чтобы существовало четыре множества строк:

• L – множество левых частей
• T – множество текстов нашего языка
• R – множество правых частей
• A – множество антислов

Далее, надо чтобы произвольная строка единственным образом представлялась ровно одним из видов:

1. A
2. T
3. LT
4. TR
5. LTR

В этом случае будет выполняться соотношение между производящими функциями:

`(xN)/(1-xN)=a(x)+(w(x))/(1-w(x))+l(x)(w(x))/(1-w(x))+(w(x))/(1-w(x))r(x)+l(x)(w(x))/(1-w(x))r(x)`

Или

`(xN)/(1-xN)=a(x)+(1+l(x))(w(x))/(1-w(x))(1+r(x))`

Договоримся прибавлять к каждой производящей функции единицу: `a(x)->1+a(x), l(x)->1+l(x), r(x)->1+r(x)`. Тогда

`1/(1-xN)=(l(x)r(x))/(1-w(x))+a(x)-l(x)r(x)`

Приведу пример. Пусть алфавит разбит на три множества X, Y, Z. Язык состоит из всех строк видов Y, XY, YZ, XZ, XXY, XYZ, YZZ, XXZ, XZZ, XXXY, XXYZ, ... – то есть словами являются буквы множества Y, а также всевозможные строки, в которых буквы идут по порядку `X -> Y -> Z` и нет двух букв из Y подряд.

Например, строка вида ZZZYZXYZZXYYXXYYZZYYXZXXXX разлагается вот так:

ZZZ   YZ   XYZZ   XY   Y   XXY   YZZ   Y   Y   XZ   XXXX

Ясно, что множество L состоит из всех строк видов Z, ZZ, ZZZ, ... . Множество R – X, XX, XXX, ... . Множество A включает в себя множества L и R, а также строки видов ZX, ZZX, ZXX, ZZXX, ... .

Короче `l(x)=1/(1-xZ), \ \ r(x)=1/(1-xX), \ \ a(x)=l(x)r(x)`.

Значит `1/(1-xN)=1/((1-w(x))(1-xX)(1-xZ))=>`

`w(x)=1-(1-x(X+Y+Z))/((1-xX)(1-xZ))`

А для каких ещё ПРЯ такое возможно? Ответом будет

Теорема 3. ПРЯ допускает подобное разложение любой строки тогда и только тогда, когда все его суффиксы текста и все приставки текста универсальны.

По теореме 1 подобное разложение существует и единственно для максимальных текстов. Если же существует другое разложение, с немаксимальным текстом, то это значит, что или существует левая часть, заканчивающаяся на приставку текста, или существует правая часть, начинающаяся на суффикс текста. Другими словами, если таких правых и левых частей нет, то все разложения единственны. С другой стороны, если хотя бы одна такая часть существует, то она, будучи приставленной к соответствующему тексту, нарушит единственность разложения. Поэтому разложение единственно тогда и только тогда, когда не существует левая часть, заканчивающаяся на приставку текста и правая часть, начинающаяся на суффикс текста.

Если все приставки текста универсальны, то из того факта, что левая часть не заканчивается на приставку максимального текста следует, что она вообще не заканчивается на приставку. Аналогично правая часть не начинается на суффикс.

Осталось доказать необходимость. Если есть, например, хотя бы одна элементарная неуниверсальная приставка p, то, значит, есть текст t₁ такой, что строка pt₁ не является текстом, а значит строка p является левой частью. Но левая часть не может заканчиваться на приставку, в том числе не может быть приставкой. Значит все элементарные приставки универсальны, а по теореме 2 отсюда следует, что все приставки универсальны. Так же с суффиксами. Теорема доказана.