Учитывая следующий язык:
L1 = { (ab)n | n ≥ 0 }
То есть L1 = { ε ab, abab, ababab, abababab, ... }
Вопрос в том, чтобы найти язык L12.
Я предполагаю, что это равно { (ab)2n | n ≥ 0 }. Это правильно? Если да, то как мне это доказать? Если нет, то почему?
Спасибо!
Язык L12 — это язык всех строк вида xy, где x L1 и y L1. Обратите внимание, что x и y не обязательно должны быть одними и теми же строками; их можно выбрать самостоятельно.
На самом деле один из вариантов состоит в том, что y = , поскольку = (ab)0. Следовательно, любая строка в L1 также должна принадлежать L12, потому что мы всегда можем соединить эту строку с .
Более того, мы можем показать, что любая строка в L12 также находится в L1. Возьмите любую строку w L12. Он должен иметь форму xy для некоторых строк x, y L1. Это означает, что мы можем написать w = xy = (ab)n(ab)m для некоторых натуральных чисел n и m. Соответственно, w = (ab)n+m, а значит, w в L1.
Мы только что доказали, что L1 L12 и что L12 L 1, откуда мы получаем, что L1 = L12. Это означает, что язык L12 совпадает с языком L1.
Надеюсь это поможет!
