Если

12

Скажем, L{0} . Тогда как мы можем доказать, что L регулярно?

Если L регулярно, то, конечно, L также регулярно. Если L конечно, то оно регулярно и снова L регулярно. Также я заметил, что для L={0pp is a prime} , L не является регулярным, L{0} и L регулярным.

Но как показать это для любого подмножества L в {0} ?

ChesterX
источник

Ответы:

9

Предположим, что L содержит два слова w1 и w2 такие, что длины этих слов |w1|и |w2|, не имеют общих факторов. Тогда мы имеем, что самое длинное слово, которое не может быть образовано путем объединения этих слов, имеет длину (|w1|1)(|w2|1)1 ( число Фробениуса). То есть, если в языке есть слова, длина которых не имеет общего множителя, то все слова определенной минимальной длины находятся в языке L . Легко видеть, что это регулярно, так как по необходимости существует конечное число классов эквивалентности в отношении неразличимости Майхилла-Нерода.

Что если длины всех слов в имеют общий фактор? Что ж, нетрудно видеть, что в таких случаях L также является регулярным. Просто отметьте, что вместо всех слов, длина которых больше некоторой минимальной длины, находящихся в L , вместо этого будет верно, что все слова, длина которых кратна GCD длины слов, будут в L , и нет слов, длина которых не кратны этой GCD, и, поскольку ( L k ) является регулярной для любого целого числа k , L также является регулярной.LLLL(Lk)kL

Это довольно неформально, но все, что вам нужно формализовать, должно быть здесь.

Patrick87
источник
4

wLLL˚wL˚L=L˚L˚L

Пусть подмножество и слова в . можно выразить как конкатенацию слов в еслиможет быть выражено в виде суммы элементов , где представляет собой набор длин слов в . Таким образом, проблема сводится к выражению целого числа в виде суммы целых чисел в определенном наборе (с разрешенными повторениями): canбыть выражено как с и ?MLwLwL|w|SNSM|w|k1s1++kmsmi,siSk1N

Это хорошо известная проблема арифметики, и ответ если коэффициенты могут быть отрицательными ( ),представима тогда и только тогда оно кратно наибольший общий делитель элементов : . С требованием неотрицательных коэффициентов это все еще справедливо для достаточно больших,(ki)kiZ|w|SgcdS|w|

Рассмотрим бесконечную последовательность определенную как . Это убывающая последовательность целых чисел (начиная с , поэтому она постоянна после определенного индекса ; и По китайской теореме об остатках любой элемент из может быть выражается как с и . Если и тогда вы можете выбрать все неотрицательные коэффициенты.(gi)iminSgi=gcd(S[0,i])gminS=minSjgj=gcdSSk1s1++kmsmi,kiZ{s1,,sm}=S[0,j]xSxs1sm

Достаточно арифметики. Пусть . Каждое слово в может быть выражено как объединение слов в , длина которых не , то есть . Так как у нас также есть , у нас есть , который является регулярным, поскольку конечен, следовательно, регулярен.L˚={wL|w|gj}LLgjLL˚L˚LL=L˚L˚


В качестве альтернативы используйте характеристику обычных языков в однобуквенных алфавитах .

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