Регулярен ли унарный язык, если его показатель является линейной функцией?

13

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

Пусть и . Моя гипотеза:L = { a f ( n )Σ : n N 0 } L  регулярно x , y N 0 : f ( n ) = x n + yΣзнак равно{a}Lзнак равно{aе(N)Σ*:NN0}

L is regularx,yN0:f(n)=xn+y

Видел ли этот вопрос научную трактовку раньше? Это "очевидно" правда / ложь?

Для меня, очевидно, направление « » верно, потому что можно просто построить DFA с состояниями которые циклически перебирают состояния x после прочтения состояний y и принимают, если он находится на номере состояния y .х + у х у уx+yxyY

SEJPM
источник
Хорошая работа, сделать это наблюдение - это то, чего я не ожидаю от обычных студентов!
Рафаэль
Согласовано. Это очень хорошее наблюдение.
Рик Декер
Это не очевидно из названия, но у нас был этот вопрос раньше, вплоть до небольшой леммы об эквивалентности: каковы возможные наборы длин слов в обычном языке?
Жиль "ТАК - перестань быть злым"

Ответы:

9

Линейное близко, но технический термин, который вы ищете, является полулинейным , то есть конечным объединением линейных множеств.

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

Для унарного языка карта париха языка - это сам язык (т. Е. Каждое слово однозначно идентифицируется по количеству букв), поэтому каждый унарный регулярный язык является полулинейным.

Другая половина доказательства показывает, что вы можете построить регулярный язык, содержащий каждое унарное полулинейное множество. Это займет немного работы, но это не слишком сложно, если вы используете регулярные выражения:

  • { к }ak распознает язык{k}
  • (ak) распознает{xkxN0}
  • R1R2 распознает если распознает и распознает , где здесь поэлементное добавлениеS1+S2R1S1R2S2+
  • р1|р2 распознает если распознает и распознает , гдездесь объединение регулярных выражений.S1S2р1S1р2S2|
jmite
источник
6

Lзнак равно{aК|Кзнак равно3N+1 или Кзнак равно7N+4}
Lзнак равно{aК|Кзнак равно4N+2 или Кзнак равно13}
Рик Декер
источник