Закрытие обычного языка при вставке

Question

Предположим, что у меня есть обычный язык L под алфавитом Σ. Как показать, что язык L 'по-прежнему является обычным языком, когда я вставляю символ посередине?

Например, L содержит строку w, которая состоит из двух подстрок u и v (w = uv). Я хочу показать, что обычный язык L 'содержит строку uxv, где x - вставленный символ.

Обратите внимание, что u и v не должны иметь одинаковую длину, а x также находится в одном и том же алфавите Σ.

Спасибо!

Answer 1

Поскольку L является регулярным, существует конечный автомат A, который его принимает. Сделайте две копии (A1 и A2) A. В A2 сделать начальное состояние не начальным. Для каждого состояния p из A1 добавьте переход p - x -> p в соответствующее состояние в A2.

Используя обозначение вашего примера, теперь A1 читает u, новый переход читает x и A2 читает v.