Полные разделимые языки
بسم الله الرحمن الرحيم 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. Полный разделим...