Выполняя текущее задание по курсу формальных языков и автоматов, я как бы застрял на упражнениях с унарными языками (надеюсь, это правильный термин), то есть на языках, которые основаны на одной букве. Я не хочу спрашивать о конкретных упражнениях, а о гораздо более общей гипотезе, с которой я столкнулся:
Пусть и . Моя гипотеза:L = { a f ( n ) ∈ Σ ∗ : n ∈ N 0 } L регулярно ⇔ ∃ x , y ∈ N 0 : f ( n ) = x ⋅ n + y
Видел ли этот вопрос научную трактовку раньше? Это "очевидно" правда / ложь?
Для меня, очевидно, направление « » верно, потому что можно просто построить DFA с состояниями которые циклически перебирают состояния x после прочтения состояний y и принимают, если он находится на номере состояния y .х + у х у у
Ответы:
Линейное близко, но технический термин, который вы ищете, является полулинейным , то есть конечным объединением линейных множеств.
Половина доказательства этого является следствием теоремы Париха , которая гласит, что любой контекстно-свободный язык имеет полулинейное отображение Париха (то есть набор векторов, содержащих вхождения каждой буквы в алфавите).
Для унарного языка карта париха языка - это сам язык (т. Е. Каждое слово однозначно идентифицируется по количеству букв), поэтому каждый унарный регулярный язык является полулинейным.
Другая половина доказательства показывает, что вы можете построить регулярный язык, содержащий каждое унарное полулинейное множество. Это займет немного работы, но это не слишком сложно, если вы используете регулярные выражения:
источник
источник