Учитывая языкЧто такое пересечение двух языков?
L1={anb2m|n,m≥1}
L2={anb3n|n≥0}
L = L1 ∩ L2
Я знаю, что L1 является регулярным языком и L2 может быть представлены КПК.
Но я не понимаю ответа, который гласит, что L is {a2nb6n|n≥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 не является обычным, но он может быть реализован с очень похожим КПК.
Возможный дубликат [Что такое пересечение двух языков с разными алфавитами?] (Http://stackoverflow.com/questions/15213955/what-is-the-intersection-of-two-languages-with-different- алфавиты) – veganaiZe
@rici, что исключает то, что я не понимаю об этом, 'L' - это в основном решение, предоставленное – totoro
@totoro: Хорошо, я попытался отредактировать ваш вопрос, чтобы уточнить, какова была ваша точка зрения. Такие вопросы действительно следует задавать на http://cs.stackexchange.com/, так как они действительно не имеют никакого отношения к программированию. Однако имейте в виду, что ваш вопрос не будет хорошо принят там, если вы не попытаетесь показать свою работу. – rici