Что такое пересечение двух языков?

Question

Учитывая языки

L1={anb2m|n,m≥1}
L2={anb3n|n≥0}

L = L1 ∩ L2

я знаю это L1 это обычный язык и L2 может быть представлен КПК.

Но я не понимаю ответ, который утверждает, что L является {a2nb6n|n≥1}, Как рассчитывалось это решение?

Answer 1

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

Оба комплекта L1 а также L2 подмножества {acount(a)bcount(b)|j,k≥0}; то есть они состоят из некоторого числа a s, за которым следует некоторое количество b s. Условие для L1 ограничивает count(b) быть положительным четным числом, так как оно должно быть 2m для некоторого целого числа m≥1, Условие для L2 ограничивает count(b) быть точно 3×count(a),

Теперь пересечение двух наборов, определенных с помощью предикатов, представляет собой набор элементов, так что оба предиката являются истинными. Так count(b) должно делиться как на 2, так и на 3, что означает, что оно должно делиться на 6; другими словами, это должно быть 6n для некоторого положительного целого числа n, А это значит, что count(a) должно быть 2n поскольку их ровно в три раза больше. Это дает вам ответ.

подобно L2, L не является регулярным, но это может быть реализовано с очень похожим КПК.