Perpotongan bahasa bebas konteks L dengan bahasa reguler M, dikatakan selalu bebas konteks. Saya memahami bukti konstruksi produk silang, tetapi saya masih belum mengerti mengapa ini bebas konteks tapi tidak teratur.
Bahasa yang dihasilkan oleh persimpangan semacam itu memiliki string yang diterima baik oleh PDA dan DFA. Karena itu diterima oleh DFA, bukankah itu harus menjadi bahasa biasa? Plus, jika persimpangan adalah biasa, itu juga berarti bebas konteks, karena semua bahasa biasa juga bebas konteks.
Adakah yang bisa menjelaskan kepada saya mengapa bahasa yang diperoleh dari persimpangan seperti itu tidak teratur?
Jawaban:
The cross product proof consists of constructing an automatonP⊗F which contains the mechanics of both P and F , and which accepts only words for which both sides accept. The cross-product automaton is a PDA (and therefore the recognized language is context-free) — intuitively, because the cross product with an n -state DFA consists of taking n copies of P and adding (q,a,[q]) arrows between matching states in P where the DFA has a arrows. The result is not a finite automaton in general (not even a non-deterministic one) because the P part relies on the stack and this reliance does not go away in P⊗F in general.
A trivial example is thatA∗ is regular, and if L is context-free but not regular then L∩A∗=L is context-free but not regular.
sumber