Cтраница 1
Слово вида uew, где и w указаны выше, будем называть специальным словом. [1]
Предложение 2.140. Каждое слово вида дп содержит ( п - 1) - ю степень правильного слова. [2]
Указанная итерация к словам вида I3fe и 13 / е 1 ( fc l) 5 не применима. [3]
Теорема 2.169. Любое бесконечное слово W содержит либо квадрат правильного слова, либо слово вида fgf, где f и g - правильные слова. [4]
Любое бесконечное слово содержит в качестве подслова либо квадрат правильного слова, либо слово вида fgf, где f и g - правильные слова. [5]
Используем это для доказательства такого факта: каждое слово из множества F эквивалентно некоторому слову вида rafh, где а и b - неотрицательные целые числа. Действительно, если задано произвольное слово из множества F, то можно применить равенство fr r2f для того, чтобы переставлять / и г, заменяя одновременно г на г2; таким путем мы можем сдвинуть все символы / вправо, а все символы г влево. [6]
Будем говорить, что алгорифм Р есть вывод системы Ze, если Р применим ко всякому кортежу и перерабатывает его в пустое слово или в слово вида U ( kam), где П - набор, k и га - натуральные числа и а - ординал. [7]
Преобразование / P Q, сопоставленное с выходным сигналом р - q, оставляет на месте все слова г, которые не содержат вхождений слова р и каждое слово вида т рг где выделенное в записи вхождение слова р является первым слева, переводит в слово ггдг2 Функции переходов и выходов дискретного преобразователя определяются следующим образом. [8]
Здесь Е2 обозначает одну из переменных команд вида 00 04 Ь [ ( ], D2 - константу сравнения вида 00 046 [ С5 ], Е1 - переменную команду вида 00 01с [ (, / ], a D1 - слово вида 00 01c [ i, 6 5 ], используемое для упран-лония числом повторений внутреннего цикла. Поскольку слово D1 зависит от г, то оно должно восстанавливаться п переадресовываться по i. Поскольку в программе будут две одинаковые переменные команды Е2, то возможна экономия команд при их восстановлении и переадресацин. [9]
Фиксируем на W ориентацию и, совершив обход границы начиная с произвольной верЩины Р, последовательно выпишем все буквы. Вернувшись в Р, получим слово W вида W af а. [10]
Если слово содержит хотя бы два вида букв, то оно содержит хотя бы одну букву первого рода. В противном случае мы можем получить из него слово вида abab, что противоречит условию. Вычеркнув все буквы второго рода, совпадающие с некоторой, получим слово из п - 1 различных букв. [11]
Нильсен [89] доказал, что любой автоморфизм группы п ( Т) индуцируется некоторым автоморфизмом свободной группы F2g9 сохраняющим подгруппу R. По теореме Магнуса [81] такой автоморфизм группы Ftg переводит слово V в слово вида K-1V K, где е 1, а K. [12]
Надо доказать, что ассоциативная алгебра, порожденная отображениями xiadyi, нильпотентна. Согласно теореме 9 пункта 6.3, существует такое N, что любое ассоциативное слово длины / V в алфавите из п букв содержит либо квадрат правильного слова, либо под слово вида fgf, где / и g - правильные слова. Докажем, что наша ассоциативная алгебра имеет индекс нильпотентности не больший, чем N. Действительно, в противном случае существует минимальное в лексикографическом смысле слово F длины N, не равное нулю. Пусть / g / - соответствующее подслово, где / - правильное, a g - пустое, либо правильное. [13]
Следовательно, существуют выводы, преобразующие и, Uo, a, VQ, v в слова х, и, w, v, у е Л соответственно. Если Г не содержит правил вида р - - 1, то UQVO f 1 влечет uv 1, а последнее гарантирует, что никакие два слова вида xu wvny не совпадают и, таким образом, L бесконечен. [14]