Напишите для десятичного расширения (без начального ). Пусть и целые числа с . Рассмотрим язык десятичных разложений кратных плюс константа:0
Является регулярными? контекстно-свободной?
(Контраст с языком графа аффинной функции )
Я думаю, что это хороший вопрос для домашней работы, поэтому ответы, которые начинаются с подсказки или двух, и объясняют не только, как решить вопрос, но и как решить, какие методы использовать, будут оценены.
formal-languages
context-free
regular-languages
integers
Жиль "ТАК - перестань быть злым"
источник
источник
Ответы:
Очень просто: предположим, что числа записаны в десятичном виде (другие основания обрабатываются тривиальной модификацией). Построение ДКА, с состояния 0, 1, ..., . Начальное состояние равно 0, и из состояния на входе цифра переходит в состояние . Принимаемое состояние - (может потребоваться настройка, если ).a a−1 q d (10q+d)moda bmoda b>a
источник
Это регулярно. Давайте сначала поработаем в двоичном формате, который будет обобщен на любую базу> 1. Пусть будет языком, о котором идет речь. Для a = 1, b = 0 получаемMa,b
это все строки над без начальных нулей, что является регулярным (создайте для него регулярное выражение).{0,1}
Теперь для любого , где b равно 0, мы получаем из , умножая численно на a, то есть выполняя преобразование для каждой строки . Это может быть сделано побитовым путем последовательности сдвигов и сложений которые зависят от битов фиксированной строки . Нам нужны две трансформации:a Ma,0 M1,0 x¯→ax¯¯¯¯¯¯ Ma,0 x a¯
а также
Конкатенация 0 справа четко сохраняет регулярность. Таким образом, нам остается только доказать, что вторая операция сохраняет регулярность. Это можно сделать с помощью конечного преобразователя, работающего на справа налево. Это самый сложный шаг. Я предлагаю делать это с помощью программы с псевдокодом и некоторой конечной вспомогательной памяти (например, с некоторыми битовыми переменными) вместо использования состояний. Пока память имеет фиксированный размер для всех входов и вы сканируете строго справа налево, это конечное преобразование состояния и сохраняет регулярность.x¯
Наконец, чтобы получить из нам нужно численно добавить к каждой строке, но это делается с помощью аналогичного преобразователя который зависит от фиксированного числа b.Ma,b Ma,0 b Tb
Чтобы сделать то же самое в любой базе, покажите дополнительно, как выполнить умножение на одну цифру в этой базе, используя преобразователь который зависит от d. При этом мы можем умножать на многозначные числа и при этом оставаться на обычных языках. Или мы можем уточнить это, сказав, что умножение на - это просто повторное сложение.d Sd d
Вы хотели только намеки. Каждый из этих шагов зависит от довольно сложной теоремы / техники, поэтому доказательство того, что они получат полное доказательство, будет дополнительной работой.
источник
Подсказка № 1 : сначала решите более популярную проблему «напишите автомат, который распознает десятичные / двоичные представления чисел, кратных 3», когда младший значащий бит появляется первым.
Промежуточный вопрос: докажите, что является регулярным.{ax+b¯¯¯¯¯¯¯¯¯¯¯¯¯¯∣ax+b≥0x∈Z}
Подсказка # 2 : график функции "по модулю " конечен. Вы можете вычислить его для каждого в который является как набором цифр, так и языком вашего автомата.a d { 0 , … , 9 }(n↦10n+d) a d {0,…,9}
Подсказка # 3 : Теперь, замените с . Что это меняет? Попробуйте использовать тот факт, что обычные языки устойчивы при пересечении, вместо того, чтобы создавать специальный автомат. x ∈ Nx∈Z x∈N
Подсказка # 4 : Предположим теперь , что простое число (так что является полем) и что мы все еще в том случае , когда . Теперь мы используем представление, где первый бит является наиболее значимым битом. Можете ли вы построить автомат таким же образом?Z / a Z x ∈ Za Z/aZ x∈Z
Подсказка № 5 : вам не всегда нужно создавать автомат, чтобы доказать, что язык является регулярным. Как вы можете использовать предыдущие результаты, чтобы доказать, что регулярно? (с наиболее значимым битом первым)M
источник
Я слежу за идеей @vonbrand:
Подсказка 1:
Решите сначала для . Вы можете использовать теорему Майхилла-Нерода .b=0
Подсказка 2:
Решите общий случай, повторно используйте автомат, индуцированный случаем .b=0
источник
Язык регулярный.
Подсказка: изгонять девятки
Доказательство идеи
Для и ,a=9 b<9
Для обработки других значений , которые взаимно просты с ,a 10
Для обработки значений которых только простые факторы и ,a 2 5
Чтобы обобщить на все значения и ,a b
Обратите внимание, что мы используем любую удобную технику; три основных элементарных метода (регулярные выражения, конечные автоматы, теоретико-множественные свойства) представлены в этом доказательстве.
Подробное доказательство
Пусть с взаимно простым с . Пусть и . По элементарной арифметике числа, равные по модулю , в точности совпадают с числами, равными по модулю и по модулю , поэтому . Поскольку пересечение регулярных языков является регулярным, иa=2p5qa′ a′ 10 M′={a′x+b¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯∣x∈Z∧a′x+b≥0} M′′={2p5qx+b¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯∣x∈Z∧2p5qx+b≥0} b a b a′ b 2p5q M∩{x¯¯¯∣x≥b}=M′∩M′′∩{x¯¯¯∣x≥b} {x¯¯¯∣x≥b} является регулярным, потому что он является дополнением конечного (следовательно, регулярного) языка, если и также регулярны, то является регулярным; и, следовательно, регулярно, так как это объединение этого языка с конечным множеством. Поэтому для завершения доказательства достаточно доказать, что и регулярны.M′ M′′ M∩{x¯¯¯∣x≥b} M M′ M′′
Начнем с , то есть числа по модулю . Целые числа, десятичное расширение которых находится в , характеризуются последними цифрами , поскольку изменение цифр далее слева означает добавление кратного который кратен . Следовательно, где - алфавит всех цифр, а - конечный набор слов длины и - это обычный язык.M′′ 2p5q M′′ max(p,q) 10max(p,q) 2p5q 0∗M′′=ℵ∗F ℵ F max(p,q) M′′=(ℵ∗F)∩((ℵ∖{0})ℵ∗)
Теперь обратимся к , то есть числа по модулю где взаимно просты с . Если то - это множество десятичных разложений всех натуральных чисел, то есть , которое является обычный язык. Теперь предположим, . Пусть . По маленькой теореме Ферма, , то есть делит . Мы строим детерминированный конечный автомат, который распознает следующим образом:M′ a′ a′ 10 a′=1 M′ M′={0}∪((ℵ∖{0})ℵ∗) a′>1 k=a′−1 10a′−1≡1moda′ a′ 10k−1 0∗M′
Состояние достигнутое из слова удовлетворяет и . Это можно доказать индукцией по слову, следуя переходам на автомате; переходы рассчитываются для этого, используя тот факт, что . Таким образом, автомат распознает десятичные разложения (с учетом начальных нулей) чисел вида с помощью ; так как , автомат распознает десятичные разложения чисел, равных по модулю позволяя начальные нули, что(i,u) x¯¯¯ i≡|x¯¯¯|modk u≡xmod10k−1 10k≡1mod10k−1 u+y10k u≡bmoda′ 10k≡1moda′ b a′ 0∗M′ . Таким образом, этот язык оказался регулярным. Наконец, является обычным языком.M′=(0∗M′)∩((ℵ∖{0})ℵ∗)
Чтобы обобщить до оснований, отличных от , замените и выше на все основные множители базы.10 2 5
Формальное доказательство
Оставлено как упражнение для читателя, в вашем любимом доказательстве теоремы.
источник