Пересечение контекста бесплатно с обычными языками

Говорят, что пересечение языка L, не зависящего от контекста, с обычным языком M всегда является контекстно-свободным. Я понял доказательство создания перекрестного продукта, но до сих пор не понимаю, почему он не контекстный, а не регулярный.

Язык, генерируемый таким пересечением, имеет строки, которые принимаются как PDA, так и DFA. Поскольку он принят DFA, разве это не должен быть обычный язык? Кроме того, если пересечение является регулярным, оно также подразумевает отсутствие контекста, поскольку все обычные языки также не зависят от контекста.

Может кто-нибудь объяснить мне, почему язык, полученный таким пересечением, не является регулярным?

Если зависит от контекста, то есть PDA P, который принимает его. Если M регулярно, то есть DFA F, который принимает его. Язык пересечения состоит из слов, которые распознаются P и $L$$\mathscr{P}$$M$$\mathscr{F}$$\mathscr{P}$$\mathscr{F}$ .

Любое слово, которое находится на пересечении, принимается , но не все слова, которые принимаются F, находятся на пересечении: только те слова, которые также принимаются $\mathscr{F}$$\mathscr{F}$$\mathscr{P}$ .

Доказательство перекрестного произведения состоит в построении автомата который содержит механику как P, так и F , и который принимает только те слова, которые принимают обе стороны. Автомат кросс-продукт представляет собой портативный компьютер (и , следовательно, признанным языком является контекстно свободной) - интуитивно, так как векторное произведение с п -state DFA состоит из взятия п копий Р и добавление ( д , , [ д ] ) стрелки между согласующими состояниями в P , где DFA имеет$\mathscr{P} \otimes \mathscr{F}$$\mathscr{P}$$\mathscr{F}$$n$$n$$\mathscr{P}$$(q,a,[q])$$\mathscr{P}$$a$стрелы. Результат не является конечным автоматом вообще (даже недетерминированным), потому что часть опирается на стек, и эта зависимость не исчезает в P ⊗ $\mathscr{P}$$\mathscr{P} \otimes \mathscr{F}$ в целом.

Тривиальным примером является то, что является регулярным, и если L не зависит от контекста, но не является регулярным, то L ∩ A ∗ = L не зависит от контекста, но не является регулярным.$\mathscr{A}^*$$L$$L \cap \mathscr{A}^* = L$