Каковы возможные наборы длин слов в обычном языке?

Для языка $L$ определите множество длин как множество длин слов в : L L S ( L ) = { | ты | | U ∈ L $L$$L$

Какие наборы целых чисел могут быть набором длины обычного языка?

Во-первых, наблюдение, которое не является решающим, но удобным: множество $\mathscr{S}$ целых множеств, которые$LS(L)$ для некоторого регулярного языка$L$ в непустом алфавите$\mathscr{A}$ , не зависит от выбора алфавита. Чтобы увидеть это, рассмотрим конечный автомат, который распознает$L$ ; длины слов, находящихся в$L$ являются длинами путей на автомате, рассматриваемых как немеченый граф из начального состояния в любое принимаемое состояние. В частности, вы можете поменять каждую стрелку на$a$ и получить обычный язык такой же длины, установленный над алфавитом$\{a\}$ . И наоборот, если$L$ - это обычный язык, состоящий из одноэлементного алфавита, его можно легко ввести в больший алфавит, и в результате все еще остается обычный язык.

Поэтому мы ищем возможные наборы длины для слов в одноэлементном алфавите. В одноэлементном алфавите язык является набором длины, записанным в унарном виде: $\mathrm{LS}(L) = \{n\in\mathbb{N} \mid a^n \in L\}$ . Такие языки называются унарными языками.

Пусть $L$ регулярный язык и рассмотрим детерминированный конечный автомат (DFA), который распознает $L$ . Набор длин слов $L$ - это набор длин путей в DFA, рассматриваемый как ориентированный граф, который начинается в начальном состоянии и заканчивается в одном из состояний принятия. DFA для одноэлементного алфавита довольно ручное (NFAs было бы более диким): это либо конечный список, либо круговой список. Если список конечен, пронумеруйте состояния от $0$ до $h$ следуя порядку списка; если он круговой, нумерация состояний от $0$ до $h$ следующих за заголовком списка, и от $h$ до $h+r$ по циклу.

Пусть $F$ - множество индексов принимаемых состояний до $h$ , а $G$ - множество индексов принимаемых состояний от $h$ до $h+r$ . потом

Обратно, пусть $h$ и $r$ два целых числа , а $F$ и $G$ два конечных множества целых чисел , таких , что $\forall x \in F, x \le h$ и$\forall x \in G, h \le x \le h+r$ . Тогда множество$L_{F,G,r} = \{ a^{k\,r+x} \mid x\in G, k\in\mathbb{N} \}$ - регулярный язык: это язык, распознаваемый DFA, описанным выше. Регулярное выражение, описывающее этот язык, представляет$a^F \mid a^{G} (a^r)^*$ .

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

¹ _{Чтобы придерживаться устоявшегося понятия , периодический означает характеристическую функцию множества (которая является функцией $\mathbb{N}\to\{\mathtt{false},\mathtt{true}\}$ которую мы поднимаем до функции$\mathbb{Z}\to\{\mathtt{false},\mathtt{true}\}$ ) является периодическим. Периодичность выше определенного значения означает, что функция ограничена$[h,+\infty[$ может быть продлен в периодическую функцию.}

Любое конечное подмножество может быть множеством длины регулярного языка L , поскольку вы можете взять унарный алфавит { 0 } и определить L как { 0 ℓ 1 , $\{\ell_1,\ldots,\ell_n\}\subset\mathbb{N}$$L$$\{0\}$$L$ (это включает пустой язык и { ε } ).$\{0^{\ell_1},\ldots,0^{\ell_n}\}$$\{\varepsilon\}$

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

Пусть - регулярные выражения, порождающие языки L 1 и L 2 соответственно. Это (вроде) легко увидеть, что$r_1,r_2$$L_1$$L_2$

• .$\mathsf{LS}(L(r_1+r_2))=\mathsf{LS}(L_1\cup L_2)=\mathsf{LS}(L_1)\cup\mathsf{LS}(L_2)$
• . Это обозначается L S ( L 1 ) + L S ( $\mathsf{LS}(L(r_1r_2))=\mathsf{LS}(L_1L_2)=\{\ell_1+\ell_2:\ell_1\in\mathsf{LS}(L_1),\ell_2\in\mathsf{LS}(L_2)\}$ .$\mathsf{LS}(L_1)+\mathsf{LS}(L_2)$
• $$\mathsf{LS}(L(r_1^*))=\{0\}\cup\bigcup_{n\geq 1}\Big\{\sum_{i=1}^n\ell_i:(\ell_1,\ldots,\ell_n)\in\big(\mathsf{LS}(L_1)\big)^n\Big\}.$$

Таким образом, возможными наборами целых чисел, которые могут быть набором длины обычного языка, являются те, которые являются конечными подмножествами или которые можно построить, взяв конечные подмножества S 1 , S 2 из N и используя предыдущие формулы конечным количество раз.$\mathbb{N}$$S_1,S_2$$\mathbb{N}$

Здесь мы используем, что регулярные языки строятся по определению, применяя правила для построения регулярного выражения конечное число раз. Обратите внимание, что мы можем начать с любого конечного подмножества , хотя в регулярных выражениях мы начинаем со слов длиной 0 и 1 только в качестве базового случая. Это легко оправдывается тем фактом, что все (конечные) слова являются (конечными) конкатенациями символов алфавита.$\mathbb{N}$

Согласно лемме прокачки для регулярных языков существует такое , что строка x длины, по крайней мере равная n, может быть записана в следующем виде: x = u v w Где выполняются следующие три условия: | ты v | < п | V | > 0 u v k w ∈ $n$$x$$n$

Это дает нам один тест для наборов: набор не может быть набором длины обычного языка, если только все его элементы не могут быть выражены как некоторый произвольный набор целых чисел, не превышающий фиксированное , плюс несколько кратных неопределенного значения m (длина из v ), плюс некоторое произвольное конечное значение.$n$$m$$v$

Другими словами, похоже, что возможными наборами языковых длин для обычных языков является замыкание по отношению к объединению множеств (как обсуждалось в EDIT и EDIT2, благодаря комментаторам) множеств, описываемых следующим образом: Для фиксированных a , b ∈ N и всех конечных множеств S по лемме прокачки для регулярных языков (спасибо Жилю за указание на глупую ошибку в моей первоначальной версии, в которой я определял множество N ).

РЕДАКТИРОВАТЬ: немного больше обсуждения. Конечно, все конечные наборы целых чисел являются наборами длины. Кроме того, объединение двух наборов длины также должно быть набором длины, как и дополнение любого набора длины (отсюда пересечение, отсюда различие). Причина этого в том, что обычные языки закрыты для этих операций. Поэтому ответ, который я даю выше, является (возможно) неполным; в действительности любое объединение таких наборов также является набором длины некоторого регулярного языка (обратите внимание, что я отказался от требования пересечения, дополнения, различия и т. д., поскольку они покрыты тем фактом, что регулярные языки закрыты под этими свойствами, так как обсуждается в EDIT3; я думаю, что на самом деле необходим только союз, даже если другие правы, что может быть не так).

EDIT2: еще больше дискуссий. Ответ, который я даю, в основном, где вы в конечном итоге, если вы взяли ответ Янома немного дальше; $bn$ часть приходит от звезды Клини, то происходит от конкатенации, и обсуждение объединения, пересечения, разности и дополнений приходят от + регулярных выражений (а также других закрывающих свойств регулярных языков) доказуемо , начиная с автоматов) ,$a$

РЕДАКТИРОВАТЬ 3: В свете комментария Яномы, давайте забудем о свойствах закрытия наборов языковых длин, которые я обсуждаю в первой редакции. Так как у обычных языков есть эти свойства замыкания, и так как у каждого обычного языка есть DFA, из этого следует, что лемма прокачки для регулярных языков применяется ко всем объединениям, пересечениям, дополнениям и различиям обычных языков, и мы оставим это при этом ; нет необходимости даже рассматривать что-либо из этого, кроме объединения, которое, я думаю, может оказаться необходимым, чтобы сделать мой оригинал (модифицированный, благодаря вкладу Жиля) правильным. Итак, мой окончательный ответ таков: то, что я говорю в оригинальной версии, плюс закрытие множеств длины языка относительно объединения множеств.