доказательство того, что язык формы 0 ^ n, где n простое число, не является ни регулярным, ни контекстно-свободным

Question

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

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

Answer 1

Предположим, что данный язык не зависит от контекста.Используя лемму прокачки для контекстно-свободных языков , вы получите числа x и y, такие что x, x + y, x + 2y, x + 3y и т. Д., Являются простыми числами.Однако это невозможно, поскольку между простыми числами есть сколь угодно большие промежутки (чтобы доказать это, рассмотрим числа n! +2, n! +3, .... n! + N для любого натурального числа n> =2 - все они составные).

Другой подход заключается в использовании теоремы о том, что каждый контекстно-свободный язык над унарным алфавитом является обычным языком.Затем рассмотрим, как могут выглядеть DFA по унарному алфавиту: каждое состояние имеет ровно одно исходящее ребро.После устранения недостижимых состояний состояния должны быть q_0, q_1, ... q_k, где переход от q_i переходит к q_ {i + 1}, для 1 <= i <k, а переход из q_k переходит в некоторое состояние.q_0 - начальное состояние.Независимо от выбранного множества конечных состояний, это не может принять {0 ^ n |n - простое число} - снова используйте тот факт, что между простыми числами есть сколь угодно большие промежутки, чтобы получить противоречие. </p>