I dont need a proof, since this is an objective exam question and allowed 2 mins only. The options are regular
or cfl
or csl
. I dont understand how to tackle this.
If we I write it as
(a^n b^n | n<100) UNION (a^n b^n | n>100)
Now call first part L1 and second part L2 and then try to compliment using,
De-morgons Law L'= L1' INTERSECTION L2'
I dont think thats the right way or a quick way considering the fact we need to spend 2-3 mins only. Any better approch to this?
That is the right way to do, L = {a^n b^n | n<100} UNION {a^n b^n | n>100}
The first part is regular and second part is DCFL. Now, L' = COMP({a^n b^n | n<100}) INTERSECT COMP({a^n b^n | n>100})
regular complement is always regular and DCFL complement is always DCFL and hence CFL.
So, Regular intersect CFL gives CFL.