Нет, пересечение двух обычных языков гарантированно будет обычным языком. Это может быть доказано многими способами, но простой способ - использовать свойства замыкания. Предположим, у вас есть обычные языки L1 и L2. Для этих языков существуют DFA M1 и M2. Измените все принимающие состояния на неприемлемые и наоборот на обеих машинах;назовем получившиеся машины М1 'и М2'. Они принимают дополнения L1 и L2, которые должны быть обычными языками (поскольку есть DFA, которые их принимают). Поскольку эти дополнения являются регулярными, для них существуют регулярные выражения r1 и r2. Тогда регулярное выражение r = r1 + r2 также описывает регулярный язык. Следовательно, он имеет DFA M. Измените все принимающие состояния на неприемлемые состояния и наоборот в M, чтобы получить M '. M 'теперь принимает обычный язык (L1' union L2 ')'. Но мы знаем Де Морганом, что это выражение эквивалентно L1, пересекающему L2.
Это конструктивное доказательство в том, что оно показывает, как построить DFA для L1, пересекающего L2, учитывая DFA для L1 и L2. Возможны и другие конструктивные доказательства. Другим популярным вариантом является использование декартово произведений машиностроения. Это даст DFA с одним состоянием для каждой пары состояний в L1 и L2, и переходы будут соответствовать парам переходов, взятых из L1 и L2.