Решать, является ли унарный контекстно-зависимый язык регулярным

Это известный результат, что вопрос

Генерирует ли контекстно-свободная грамматика обычный язык?

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

Мой вопрос состоит в том, чтобы знать, что происходит с унарными контекстно-зависимыми языками.

Можно ли определить, порождает ли данная контекстно-зависимая грамматика в унарном алфавите регулярный язык?

Если ответ положительный, оценка сложности будет приветствоваться.

Увы, ваша проблема неразрешима. Подход, на который я наткнулся (который может быть перегружен, поэтому любой, кто имеет более целесообразный подход, должен подойти!) Сначала использует диагональный аргумент, чтобы продемонстрировать, что существует одинарный CSL который не является регулярным (в отличие от положительного результата для унарных КЛЛ), а затем уменьшает проблему остановки для машин Тьюринга, создавая для ТМ конструкцию CSG которая имитирует на длине ленты, меньшей длины строки синтаксического анализа , распознавая если останавливается без превышения своих границ и не удалось проанализировать иначе, так что успешно анализирует всеM G M w X M G w ∈ $X$$M$$G$$M$$w$$X$$M$$G$$w \in X$достаточно длинные, если останавливается (так что отличается от только конечным числом строк и, следовательно, не может быть регулярным), в противном случае распознает пустой язык (который явно регулярен).L ( G ) X $M$$L(G)$$X$$G$

Ключом к этому подходу является наблюдение, что CSG не просто занимаются грамматическими вопросами, такими как структура фраз - действительно, последовательности вывода CSG могут выполнять произвольные недетерминированные вычисления, ограниченные пространством (действительно, есть$\mathbf{PSPACE}$-полные CSL), прежде чем приступить к выравниванию со строкой разбора. Это легче всего наблюдать с помощью стандартных преобразований между CSG и монотонными грамматиками (которые продолжают работать, если они ограничены унарными алфавитами) и использованием простых монотонных производств для моделирования машинных переходов Тьюринга на строках деривации, которые представляют этапы в истории вычислений. В этом ответе я собираюсь предположить, что читатель может интуитивно понять большинство деталей, когда требуется CSG для имитации данного вычисления. (Я полагаю, что спрашивающему все это удобно, но я рассмотрю его для полноты. Тем не менее, не стесняйтесь просить разъяснения в комментариях.)

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

Пусть будет перечислением DFA по алфавиту , так что число состояний в увеличивается в . Мы описываем CSG с точки зрения его поведения при разборе строки :{ 1 } D i i G X 1 n ∈ { 1 } $D_1, D_2, ...$$\{1\}$$D_i$$i$$G_X$$1^n \in \{1\}^*$

1. Недетерминированные генерируют строку из «пустых» нетерминалов, которые мы считаем «лентой». Один из пустых нетерминалов должен быть отдельным нетерминалом «пусто + головка чтения-записи + начальное состояние». Если строка синтаксического анализа не то эта деривация закончится неудачей. Мы опишем остальную часть процесса в терминах детерминированных вычислений, смоделированных единственным возможным выводом.1 $n$$1^n$
2. Напечатайте на ленте кодировку за которой следует число , где и выбраны так, чтобы на нашей ленте всегда было достаточно места, чтобы сделать то, что нам нужно. (Это возможно, поскольку пространство, необходимое для кодирования как и логарифмически увеличивается в .) i i = n - c c D i i $D_i$$i$$i = n - c$$c$$D_i$$i$$i$
3. Оцените на входе . Это не требует представления - вы можете просто сохранить одно состояние, которое вы меняете в соответствии с переходами при уменьшении .1 я Д я Д я$D_i$$1^i$$D_i$$D_i$$i$
4. Если отклоняет , перезаписать всю ленту нетерминалами, которые выдают . Иначе не получится.1 I$D_i$ $1^i$$1$

Мы берем . Ясно, что для любого , поскольку .X ≠ L ( D i ) i 1 i + c ∈ X ⇔ 1 i + c ∉ L ( D i$X = L(G_X)$$X \ne L(D_i)$$i$$1^{i+c} \in X \Leftrightarrow 1^{i+c} \notin L(D_i)$

Следующим шагом является разработка сокращения от проблемы остановки до проблемы задающего. (Если вы пропустили раздел, пусть будет произвольным нерегулярным унарным CSL, сгенерированным CSG .)G $X$$G_X$

Пусть произвольный TM. Мы конвертируем в CSG который ведет себя следующим образом при разборе строки :M G 1 $M$$M$$G$$1^n$

1. Создайте пустых нетерминалов, крайний левый - отдельный нетерминал + нетерминал головки чтения-записи, а также сгенерируйте «граничный» нетерминал на каждой стороне. Опять же, если мы сгенерируем неправильное количество нетерминалов, мы потерпим неудачу.$n-2$
2. Смоделируйте в пространстве между граничными нетерминалами. Если когда-либо переключается на одно из граничных состояний, мы прекращаем моделирование и предполагаем, что никогда не останавливается.М $M$$M$$M$
3. Если останавливается, себя как . Если мы должны были прекратить симуляцию, то потерпели неудачу.G $M$$G_X$

Обратите внимание, что если удастся вечно работать в границах, то никогда не сможет сгенерировать строку разбора, и поэтому потерпит неудачу. Если останавливается, то существует некоторое количество пространства которого достаточно, чтобы вместить все вычисления , следовательно, анализирует всякий раз, когда и , и, следовательно, является объединением и конечный язык, поэтому не является регулярным. С другой стороны, если никогда не останавливается, то явно регулярно.G M n M G 1 m m ≥ n + 2 1 m ∈ X X L ( G ) L ( G ) M L ( G ) = $M$$G$$M$$n$$M$$G$$1^m$$m \ge n+2$$1^m \in X$$X$$L(G)$$L(G)$$M$$L(G) = \varnothing$

Алгоритм для определения того, является ли регулярным или нет, будет определять, останавливается ли на чистой ленте, что неразрешимо. Отсюда следует, что проблема Аскера неразрешима.$L(G)$$M$

По сути, это тот же ответ, что и выше, но, поскольку ищется «более целесообразный» ответ, я упоминаю следующее: (Кроме того, это мой первый пост здесь, так что извините, если я публикую тривиальность!)

Заметьте, что пустота неразрешима для унарных контекстно-зависимых языков. Исправить контекстно-зависимый, но нестандартный язык . Учитывая LBA для , можно легко построить LBA для . Тогда ясно, что регулярно тогда и только тогда, когда пусто.$N\subseteq a^*$$L\subseteq a^*$$L'=\{ a^n \mid \text{$a^n\in N$ and $\exists m\le n\colon a^m \in L$}\}$$L'$$L$

Обновление: Конечно, тот же аргумент показывает, что неразрешимость уже имеет место для детерминированного логарифмического пространства.