Язык значений аффинной функции

10

Напишите для десятичного расширения (без начального ). Пусть и целые числа с . Рассмотрим язык десятичных разложений кратных плюс константа:n¯n0aba>0a

M={ax+b¯xN}

Является регулярными? контекстно-свободной?M

(Контраст с языком графа аффинной функции )

Я думаю, что это хороший вопрос для домашней работы, поэтому ответы, которые начинаются с подсказки или двух, и объясняют не только, как решить вопрос, но и как решить, какие методы использовать, будут оценены.

Жиль "ТАК - перестань быть злым"
источник
Только сейчас я понимаю, что ответил на конкретный случай, следуя идее @vonbrand. DFA, который принимает десятичные представления натурального числа, делимого на 43
Хендрик

Ответы:

9

Очень просто: предположим, что числа записаны в десятичном виде (другие основания обрабатываются тривиальной модификацией). Построение ДКА, с состояния 0, 1, ..., . Начальное состояние равно 0, и из состояния на входе цифра переходит в состояние . Принимаемое состояние - (может потребоваться настройка, если ).aa1qd(10q+d)modabmodab>a

vonbrand
источник
1
Очень мило - намного лучше, чем у меня!
Дэвид Льюис
8

Это регулярно. Давайте сначала поработаем в двоичном формате, который будет обобщен на любую базу> 1. Пусть будет языком, о котором идет речь. Для a = 1, b = 0 получаемMa,b

M1,0={1,10,11,100,101,...}

это все строки над без начальных нулей, что является регулярным (создайте для него регулярное выражение).{0,1}

Теперь для любого , где b равно 0, мы получаем из , умножая численно на a, то есть выполняя преобразование для каждой строки . Это может быть сделано побитовым путем последовательности сдвигов и сложений которые зависят от битов фиксированной строки . Нам нужны две трансформации:aMa,0M1,0x¯ax¯Ma,0xa¯

x¯2x¯ который являетсяx¯x¯0

а также

x¯2x+x¯

Конкатенация 0 справа четко сохраняет регулярность. Таким образом, нам остается только доказать, что вторая операция сохраняет регулярность. Это можно сделать с помощью конечного преобразователя, работающего на справа налево. Это самый сложный шаг. Я предлагаю делать это с помощью программы с псевдокодом и некоторой конечной вспомогательной памяти (например, с некоторыми битовыми переменными) вместо использования состояний. Пока память имеет фиксированный размер для всех входов и вы сканируете строго справа налево, это конечное преобразование состояния и сохраняет регулярность.x¯

Наконец, чтобы получить из нам нужно численно добавить к каждой строке, но это делается с помощью аналогичного преобразователя который зависит от фиксированного числа b.Ma,bMa,0bTb

Чтобы сделать то же самое в любой базе, покажите дополнительно, как выполнить умножение на одну цифру в этой базе, используя преобразователь который зависит от d. При этом мы можем умножать на многозначные числа и при этом оставаться на обычных языках. Или мы можем уточнить это, сказав, что умножение на - это просто повторное сложение.dSdd

Вы хотели только намеки. Каждый из этих шагов зависит от довольно сложной теоремы / техники, поэтому доказательство того, что они получат полное доказательство, будет дополнительной работой.

Дэвид Льюис
источник
Ваш FA не получает в качестве входных данных, поэтому я не вижу, как то, что вы пишете, показывает, что язык под рукой является обычным. Обратите внимание, что не каждая программа, использующая ограниченную память, соответствует FA: важно, чтобы она проходила только один раз и слева направо над входом, рассматривая каждый входной символ ровно один раз. x¯
Рафаэль
@ Рафаэль Вы можете идти справа налево, если хотите, важно быть последовательным. Я не могу найти изъян в наброске доказательства Дэвида; Вызов преобразователей немного менее элементарен, чем я предполагал, но выглядит правдоподобно.
Жиль "ТАК ... перестать быть злым"
@ Жиль: Прежде всего, он не объясняет, как перемежать умножение на и добавление к результату за один проход ; он даже уменьшает умножение на до «последовательности сдвигов и сложений ». Каждый сдвиг и дополнение в порядке, но как сделать последовательность? Во-вторых, и что еще более важно, он показывает, как построить преобразователь, который вычисляет ; что это не сразу даст вам FA , который принимает . Например, умножение чисел легко, а факторинг (якобы) нет. Так что вам нужен хотя бы дополнительный аргумент. б х ˉ х¯ х + Ь Мabax x¯ax+b¯ M
Рафаэль
Я не строю FSA. Я начинаю с набора, который легко показывается регулярным ( ), а затем преобразую все строки в нем с помощью конечного ряда операций, каждая из которых сохраняет регулярность. Это требует ряда проходов (преобразователей). Но это нормально, поскольку последовательность преобразователей и структура каждого из них фиксированы заранее, основываясь только на и . Каждый проход (преобразователь) сохраняет регулярность, поэтому нет необходимости чередовать их за один проход. Да не "элементарно". Но создание FSA за один раз, за ​​один проход было бы ужасно сложным. а бM1,0ab
Дэвид Льюис,
1
@ Рафаэль - да, это очень мощно. На самом деле, многие нерегулярные семейства также замкнуты относительно конечных преобразователей. И вы можете использовать преобразователи в качестве механизмов сокращения, получая целую теорию «структурной» сложности нерегулярных языков.
Дэвид Льюис
8

Подсказка № 1 : сначала решите более популярную проблему «напишите автомат, который распознает десятичные / двоичные представления чисел, кратных 3», когда младший значащий бит появляется первым.

Промежуточный вопрос: докажите, что является регулярным.{ax+b¯ax+b0xZ}

Подсказка # 2 : график функции "по модулю " конечен. Вы можете вычислить его для каждого в который является как набором цифр, так и языком вашего автомата.a d { 0 , , 9 }(n10n+d)ad{0,,9}

Подсказка # 3 : Теперь, замените с . Что это меняет? Попробуйте использовать тот факт, что обычные языки устойчивы при пересечении, вместо того, чтобы создавать специальный автомат. x NxZxN

Подсказка # 4 : Предположим теперь , что простое число (так что является полем) и что мы все еще в том случае , когда . Теперь мы используем представление, где первый бит является наиболее значимым битом. Можете ли вы построить автомат таким же образом?Z / a Z x ZaZ/aZxZ

Подсказка № 5 : вам не всегда нужно создавать автомат, чтобы доказать, что язык является регулярным. Как вы можете использовать предыдущие результаты, чтобы доказать, что регулярно? (с наиболее значимым битом первым)M

jmad
источник
Не стесняйтесь комментировать, если вы считаете, что это не подходит.
Джмад
Подсказка № 1 - большой шаг. В подсказке № 4 важно понимать, что и различны. Пройдя через чувствуете себя как обходной путь, вы должны управлять знаковым символом: почему бы не остаться в ? 10 Z Нa{2,5}a10ZN
Жиль "ТАК - перестань быть злым"
@ Жиль: я хотел сказать когда и , потому что утомительно распознавать. х+б0хZ3х+1234ax+b¯ax+b0xZ3x+1234
Джмад
@ Жиль: Я думаю, что Подсказка № 1 слишком крута, чтобы быть испорченной. Вы, вероятно, правы насчет подсказки № 4.
Джмад
5

Я слежу за идеей @vonbrand:

Подсказка 1:

Решите сначала для . Вы можете использовать теорему Майхилла-Нерода .b=0

Определим следующее соотношение . Это, очевидно, отношение эквивалентности. Кроме того, оно является правомерным, поскольку, если мы добавим цифру мы получим . Наконец, он насыщает , поскольку является классом эквивалентности . Поскольку имеет конечное число классов, по теореме Майхилла-Нерода мы имеем регулярность. Ассоциированный FSA является минимальным и имеет состояние.x¯y¯:xymodadx¯y¯10x+d10y+dmodax¯dy¯dLL[0]a

Подсказка 2:

Решите общий случай, повторно используйте автомат, индуцированный случаем .b=0

Мы знаем, что язык является регулярным для . Поэтому просто взять состояние FSA для языка. Теперь мы строим FSA для . Предположим, что имеет цифр. Тогда FSA разветвляется как 10-ти дерево глубины и содержит все пути к числам с цифрами. Все состояния, которые могут быть достигнуты с числом не в форме , отклоняются, в противном случае принимаются. Наконец, мы соединяем древовидную часть FSA с автоматом , в соответствии с остатком делением на .b=0aMb=0Lbkkkax+bMa

A.Schulz
источник
Я понимаю технику, но не детали. Разве Подсказка 1 также не касается случая ? Кроме того, для мод 10 , я бы ожидать 10 государств (не )? a=1a
Хендрик Ян
3

Язык регулярный.

Подсказка: изгонять девятки


Доказательство идеи

Для и ,a=9b<9

построить автомат с состояниями, обозначенными от до . - начальное состояние, а одно конечное состояние - . Из состояния , на цифре , переход в состояние .9080bsd(s+d)mod9

Для обработки других значений , которые взаимно просты с ,a10

группируйте цифры в пакетах, чтобы найти некоторое такое, что делит (например, возьмите если потому что ).ka10k1k=3a=37999=27×37

Для обработки значений которых только простые факторы и ,a25

обратите внимание, что это все о конечном числе цифр в конце.

Чтобы обобщить на все значения и ,ab

используйте тот факт, что объединение и пересечение регулярных языков являются регулярными, что конечные языки являются регулярными, и что кратные являются , кратными обоим, когда и взаимно просты.a1a2a1a2

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


Подробное доказательство

Пусть с взаимно простым с . Пусть и . По элементарной арифметике числа, равные по модулю , в точности совпадают с числами, равными по модулю и по модулю , поэтому . Поскольку пересечение регулярных языков является регулярным, иa=2p5qaa10M={ax+b¯xZax+b0}M={2p5qx+b¯xZ2p5qx+b0}babab2p5qM{x¯xb}=MM{x¯xb}{x¯xb}является регулярным, потому что он является дополнением конечного (следовательно, регулярного) языка, если и также регулярны, то является регулярным; и, следовательно, регулярно, так как это объединение этого языка с конечным множеством. Поэтому для завершения доказательства достаточно доказать, что и регулярны.MMM{x¯xb}MMM

Начнем с , то есть числа по модулю . Целые числа, десятичное расширение которых находится в , характеризуются последними цифрами , поскольку изменение цифр далее слева означает добавление кратного который кратен . Следовательно, где - алфавит всех цифр, а - конечный набор слов длины и - это обычный язык.M2p5qMmax(p,q)10max(p,q)2p5q0M=FFmax(p,q)M=(F)(({0}))

Теперь обратимся к , то есть числа по модулю где взаимно просты с . Если то - это множество десятичных разложений всех натуральных чисел, то есть , которое является обычный язык. Теперь предположим, . Пусть . По маленькой теореме Ферма, , то есть делит . Мы строим детерминированный конечный автомат, который распознает следующим образом:Maa10a=1MM={0}(({0}))a>1k=a110a11modaa10k10M

  • Состояния: . Первая часть представляет позицию цифры, а вторая часть представляет число по модулю .[0,k1]×[0,10k2]10k1
  • Исходное состояние .(0,0)
  • Существует переход, помеченный из в тогда и только тогда, когда и .d(i,u)(j,v)vd10i+umod10k1ji+1modk
  • Состояние является конечным, если (обратите внимание, что делит ).(i,u)ubmodaa10k1

Состояние достигнутое из слова удовлетворяет и . Это можно доказать индукцией по слову, следуя переходам на автомате; переходы рассчитываются для этого, используя тот факт, что . Таким образом, автомат распознает десятичные разложения (с учетом начальных нулей) чисел вида с помощью ; так как , автомат распознает десятичные разложения чисел, равных по модулю позволяя начальные нули, что(i,u)x¯i|x¯|modkuxmod10k110k1mod10k1u+y10kubmoda10k1modaba0M . Таким образом, этот язык оказался регулярным. Наконец, является обычным языком.M=(0M)(({0}))

Чтобы обобщить до оснований, отличных от , замените и выше на все основные множители базы.1025

Формальное доказательство

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

Жиль "ТАК - перестань быть злым"
источник