Skip to main content
Computer Science

Return to Question

edited body
Source Link
user82869
user82869

I am following a course on complexity theory where languages are a part of the course. There is a proof that no matter how hard I try to understand, it is till so complex that I cannot make it to half of the proof. Namely, the proocproof of the statement that the intersection of a CFL and a regular language is again CFL.

The proof that is provided to us is 2-3 pages of pure text and notations. The ones online are also heavily dependent on much notations and unfortunately, Sipser does not handle it in his book Introduction to the theory of computation. I'm wondering if there's a straight-forward and less-dependent-on-notation proof that someone knows that will contribute to understanding the proof or even reproducing it. Because at this moment, I don't even understand the proof.

I am following a course on complexity theory where languages are a part of the course. There is a proof that no matter how hard I try to understand, it is till so complex that I cannot make it to half of the proof. Namely, the prooc of the statement that the intersection of a CFL and a regular language is again CFL.

The proof that is provided to us is 2-3 pages of pure text and notations. The ones online are also heavily dependent on much notations and unfortunately, Sipser does not handle it in his book Introduction to the theory of computation. I'm wondering if there's a straight-forward and less-dependent-on-notation proof that someone knows that will contribute to understanding the proof or even reproducing it. Because at this moment, I don't even understand the proof.

I am following a course on complexity theory where languages are a part of the course. There is a proof that no matter how hard I try to understand, it is till so complex that I cannot make it to half of the proof. Namely, the proof of the statement that the intersection of a CFL and a regular language is again CFL.

The proof that is provided to us is 2-3 pages of pure text and notations. The ones online are also heavily dependent on much notations and unfortunately, Sipser does not handle it in his book Introduction to the theory of computation. I'm wondering if there's a straight-forward and less-dependent-on-notation proof that someone knows that will contribute to understanding the proof or even reproducing it. Because at this moment, I don't even understand the proof.

typos
Source Link
Thinh D. Nguyen
Thinh D. Nguyen
  • 2.3k
  • 3
  • 24
  • 71

I'mI am following a course on complexity theory where languages are a part of the course. There's this oneThere is a proof that no matter how longhard I try to understand, it's stillit is till so complex that I don'tcannot make it to half of the proof. Namely, the one provingprooc of the statement that the intersection of a CFL and a regular language is again CFL. 

The proof that is provided to us is 2-3 pages of pure text and notations. The ones online are also heavily dependent on much notations and unfortunateunfortunately, Sipser doesn'tdoes not handle it in his book introductionIntroduction to the theory of computation. I'm wondering if there's a straight-forward and less-dependent-on-notation proof that someone knows that will contribute to understanding the proof or even reproducing it. Because at this moment, I don't even understand the proof.

I'm following a course on complexity theory where languages are a part of the course. There's this one proof that no matter how long I try to understand, it's still so complex that I don't make it to half of the proof. Namely, the one proving that the intersection of a CFL and a regular language is CFL. The proof that is provided to us is 2-3 pages of pure text and notations. The ones online are also heavily dependent on much notations and unfortunate, Sipser doesn't handle it in his book introduction to the theory of computation. I'm wondering if there's a straight-forward and less-dependent-on-notation proof that someone knows that will contribute to understanding the proof or even reproducing it. Because at this moment, I don't even understand the proof.

I am following a course on complexity theory where languages are a part of the course. There is a proof that no matter how hard I try to understand, it is till so complex that I cannot make it to half of the proof. Namely, the prooc of the statement that the intersection of a CFL and a regular language is again CFL. 

The proof that is provided to us is 2-3 pages of pure text and notations. The ones online are also heavily dependent on much notations and unfortunately, Sipser does not handle it in his book Introduction to the theory of computation. I'm wondering if there's a straight-forward and less-dependent-on-notation proof that someone knows that will contribute to understanding the proof or even reproducing it. Because at this moment, I don't even understand the proof.

Source Link
user82869
user82869

Is there a *simple* proof that the intersection of a CFL and a regular language is a CFL?

I'm following a course on complexity theory where languages are a part of the course. There's this one proof that no matter how long I try to understand, it's still so complex that I don't make it to half of the proof. Namely, the one proving that the intersection of a CFL and a regular language is CFL. The proof that is provided to us is 2-3 pages of pure text and notations. The ones online are also heavily dependent on much notations and unfortunate, Sipser doesn't handle it in his book introduction to the theory of computation. I'm wondering if there's a straight-forward and less-dependent-on-notation proof that someone knows that will contribute to understanding the proof or even reproducing it. Because at this moment, I don't even understand the proof.