Регулярность языка, построенного из A KING Regular Language

Question

Я работаю через такие вопросы учебника на регулярных языках, и столкнулся с проблемой, которая составляет регулярное, учитывая следующий язык, учитывая, что $ a $ обычный язык: $$ \ {x | \ существует n \ ge 0 \; \ существует у \ в \; y= x ^ n \} $$

Я пытался показать, что это регулярно противоречит, используя MyHill-Nerode, предполагая, что он имеет бесконечный индекс, и показывает это означает, что $ a $ Должен иметь бесконечный индекс. Однако я не могу получить это доказательство работать, потому что принятие представителей каждого класса позволяет мне показать бесконечное количество пар элементов в $ a $ , которые не входят в Один и тот же класс, но эти элементы не совсем не соответствуют моим представителям, поэтому я не могу показать, что элемент не в том же классе, что и бесконечно много других.

Однако книга, кажется, указывает на то, что решение должно быть строительным. Я также могу легко увидеть конструкцию для NFA, если был зафиксирован $ n $ , но это не предлагать никакой помощи, так как это заставляет состояния зависеть от < SPAN CLASS= «Математический контейнер»> $ n $ (с использованием кортежей состояний и одновременно движущихся состояний один раз).

Если кто-то может предложить, как построить необходимые автоматы, это было бы очень полезно.

Answer 1

Как вы упоминаете, если $ n $ был исправлен, то это не слишком сложно доказать. Итак, идея будет показывать, что на самом деле $ n $ может быть ограничено априори, в зависимости от $ $ , а не на $ x $ .

С этой целью рассмотрим некоторое слово $ x \ in \ sigma ^ * $ и предположим, что $ x ^ m \ in $ для некоторых $ m $ . Пусть $ k $ - количество состояний в некоторой DFA $ d $ для $ m> k $ , то существует $ 0 \ le i такое, что Запуск $ d $ на $ x ^ i $ достигает того же состояния, что и на $ x ^ j $ . Но это подразумевает, что $ x ^ {m- {ji}} $ также принимается $ d $ ,

Таким образом, достаточно рассмотреть $ n \ lek $ . Так что вы можете переписать ваш язык как $$ \ {x | \ существует n \ le k, \ x ^ n \ in \} $$ И это регулярно.