Вставка обычного языка в другой обычный язык

Question

Пусть L1 и L2 будут обычными языками над алфавитом {a,b}. Мы определяем язык L3 следующим образом:

L3 = {pqr | pr ∈ L1, q ∈ L2}

L3 получается путем вставки строки из L2 внутри строки из L1 . Является ли язык L3 регулярным или нет?

Я пытаюсь решить эту проблему. Можно ли доказать это, используя свойство подстановки строк или гомоморфизм регулярного языка? Есть ли лучший и более простой способ доказать это?

Answer 1

Это высокоуровневое описание конструкции, показывающее, что NFA принимает L3.

Пусть M1 и M2 минимальные DFA, такие что L (M1) = L1 и L (M2) = L2 , Скопируйте M1, чтобы было две копии, M1 [1] и M1 [2]. Скопируйте M2, чтобы были | Q1 | копии M2 [1], M2 [2],…, M2 [| Q1 |]. Также нумерация состояний q1, q2,…, q | Q1 | М1. Теперь создайте NFA для M3 следующим образом:

1. Из состояния qk M1 [1] добавьте лямбда / эпсилон-переход в начальное состояние M2 [k]
2. Из принимая состояние (я) M2 [k], добавьте лямбда / эпсилон-переходы в состояние qk M1 [2]
3. Принимающие состояния - это принимающие состояния M1 [2]
4. Начальное состояние - это начальное состояние M1 [1].

Этот NFA читает некоторые входные данные, а затем недетерминированно переходит к экземпляру M2. Затем он читает строку в M2 и возвращается к тому месту, на котором остановился в следующей копии M1, где он может принять. Этот NFA имеет число состояний, равное 2 | Q1 | + | Q1 | * | Q2 |.