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

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

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

L = L1 ∩ L2
Я знаю, что L1 является регулярным языком и L2 может быть представлен КПК. Но я не понимаю ответа, который гласит, что L является {a2nb6n|n≥1}. Как было вычислено это решение?
1 3
formal-languages intersection

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, Поскольку существует ровно в три раза больше b s. предоставленный ответ.

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

4