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

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

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

L = L1 ∩ L2

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

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


union intersection automaton formal-languages
person totoro    schedule 16.02.2017    source источник
comment
Возможный дубликат Что такое пересечение двух языков с разными алфавиты?   -  person veganaiZe    schedule 16.02.2017
comment
@rici, это именно то, чего я не понимаю, L в основном это предоставленное решение   -  person totoro    schedule 17.02.2017
comment
@totoro: Хорошо, я попытался отредактировать ваш вопрос, чтобы было понятнее, в чем заключалась ваша путаница. Такие вопросы действительно следует задавать на cs.stackexchange.com, так как они не имеют ничего общего с программированием. Однако имейте в виду, что ваш вопрос не будет хорошо принят там, если вы не попытаетесь показать свою работу.   -  person rici    schedule 17.02.2017

Ответы (1)


arrow_upward
7
arrow_downward

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

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

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

Как и L2, L не штатный, но может быть реализован на очень похожем КПК.

person rici    schedule 17.02.2017