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

15

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

LS(L)={|u|uL}

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

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

Ответы:

14

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

Поэтому мы ищем возможные наборы длины для слов в одноэлементном алфавите. В одноэлементном алфавите язык является набором длины, записанным в унарном виде: LS(L)знак равно{NN|aNL} . Такие языки называются унарными языками.

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

автомат в форме списка

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

LS(L)знак равноF{Кр+Икс|Иксграмм,КN}

Обратно, пусть час и р два целых числа , а F и грамм два конечных множества целых чисел , таких , что ИксF,Иксчас иИксграмм,часИксчас+р . Тогда множествоLF,грамм,рзнак равно{aКр+Икс|Иксграмм,КN} - регулярный язык: это язык, распознаваемый DFA, описанным выше. Регулярное выражение, описывающее этот язык, представляетaF|aграмм(aр)* .

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

¹ Чтобы придерживаться устоявшегося понятия , периодический означает характеристическую функцию множества (которая является функцией N{еaLsе,TрUе} которую мы поднимаем до функцииZ{еaLsе,TрUе} ) является периодическим. Периодичность выше определенного значения означает, что функция ограничена[час,+[ может быть продлен в периодическую функцию.

Жиль "ТАК - перестань быть злым"
источник
Ваше наблюдение о неуместности алфавита предполагает, что теорема Париха может быть применена. В частности, вы показываете, что LS (L) = LS (L '), где в L' все буквы свернуты в один алфавит. Но LS (L ') - это парихское отображение языка L, которое, как известно, является полулинейным для любого регулярного языка.
Суреш
Хороший подход! 1) Я думаю, что первый абзац можно заменить, отметив, что регулярные языки закрыты от гомоморфизмов строк. 2) Для ясности вам следует рассмотреть возможность задания второй части как { h + k r + ( x - h ) } по модулю «ошибка на одну ошибку». 3) Что такое "периодический" набор целых чисел? LS(L){час+Кр+(Икс-час)|...}
Рафаэль
1
@Suresh, Raphael (1): Я предпочитаю изложить доказательство элементарно, ни гомоморфизмы, ни отображения Париха не упоминались в моем классе CS 102.
Жиль "ТАК - перестань быть злым"
@Raphael (2) Когда вы начинаете индексирование не имеет значения, я мог бы удалить условие h G , так как F может поглощать столько маленьких элементов, сколько мы хотим. (3) Набор, который является периодическим выше определенного значения, является тем, который может быть помещен в отображаемую форму выше. граммчасграммF
Жиль "ТАК - перестань быть злым"
5

Любое конечное подмножество может быть множеством длины регулярного языка L , поскольку вы можете взять унарный алфавит { 0 } и определить L как { 0 1 , {1,...,N}NL{0}L (это включает пустой язык и { ε } ).{01,,0n}{ε}

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

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

  • .LS(L(r1+r2))=LS(L1L2)=LS(L1)LS(L2)
  • . Это обозначается L S ( L 1 ) + L S ( LLS(L(r1r2))знак равноLS(L1L2)знак равно{1+2:1LS(L1),2LS(L2)} .LS(L1)+LS(L2)
  • LS(L(r1))={0}n1{i=1ni:(1,,n)(LS(L1))n}.

Таким образом, возможными наборами целых чисел, которые могут быть набором длины обычного языка, являются те, которые являются конечными подмножествами или которые можно построить, взяв конечные подмножества S 1 , S 2 из N и используя предыдущие формулы конечным количество раз.NS1,S2N

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

Janoma
источник
Я не вижу окончательного ответа. (Вы собирались закончить свой ответ позже?) Я надеялся на простое описание возможных наборов и связь с автоматами.
Жиль "ТАК - перестань быть злым"
Окончательный ответ там: «Таким образом, возможные наборы целых чисел ...». Это действительно простое описание, хотя оно связано с регулярными выражениями, а не с автоматами.
Яном
Есть более простое описание, которое не предполагает фиксацию. Может быть, этот вопрос не такой элементарный, как я думал!
Жиль "ТАК ... перестать быть злым"
Я не думаю, что вы можете избежать последнего правила, поскольку именно оператор звезды может генерировать бесконечные множества длины, точно так же, как и бесконечные языки.
Janoma
@ Жиль Итак, вы хотите замкнутую форму наименьшей фиксированной точки индуктивного решения, которое предоставляет Янома?
Рафаэль
2

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

x=uvw
|uv|<n
|v|>0
uvkwL

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

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

{a+bn|nN}S
a,bNSN

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

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

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

Patrick87
источник
1
находится на правильном пути, но вы получили квантор неправильно гдето, вы генерируете N . {a+bna,b,nN}SN
Жиль "ТАК ... перестать быть злым"
1
Анализ для дополнения набора длины может быть немного деликатным. Если над алфавитом Σ = { , Ь } , то длина множество L является N , а длина набора ¯ L является Н + , и они не дополняют друг друга. L=L(a)Σ={a,b}LNL¯N+
Janoma
@Gilles Но набор всех натуральных чисел - это допустимая длина, верно? Я не генерирую все подмножества натуральных чисел, верно? Я согласен, что это было бы проблематично. Редактировать: о, подождите, я понимаю, что вы говорите. Да, ты прав. Исправит, когда снова за компьютером.
Patrick87
@Janoma Отличный вопрос, нужно подумать, как это может изменить набор вещей, которые я определяю ...
Patrick87