#doubt

Question

Q .find which is DCFL/CFL/CSL ?? and How to find tell me procedure??

1.     { a^m b^n c^p d^q  /  m<n & p<q }   

2.     { a^m b^n c^p d^q  /  m<n or p<q }  

3.    { w1 # w2 # w3 /  |w1| =|w2| or |w1| =| w3| }

4.    { w1 # w2 # w3 /  |w1| =|w2| and  |w1| =| w3| }

5     { w1 w2 w3 /  |w1| =|w2| and  |w1| =| w3| }

6.    { w1w2 / |w1| = |w2|  }

7     { w1 # w2 / |w1| = |w2|  }

8.   { w1 # w2 # w3 /  w1 =w2  }

plz explain how to approach??

Comments

1) DCFL ,CFL and CSL

First we use stack for comparing number of a's and b's and then use the same stack for comparing c and d

2) CFL and CSL but not DCFL

this is same as first one but here there are 3 possible cases

case i) m<n

case ii) p<q

case iii) m<n and p<q

since there are 3 cases we cant decide to which case the string belongs so it is not dcfl

3) CFL , CSL but not DCFL

same here 3 cases are possible

now consider 3rd case i.e. |w1|=|w2| and |w2|=|w3|. According to this case u will think there are two dependent comparisons so it is CSL but not CFL. But it is not the case if a string satisfies 3rd case then it will also satisfy first 2 cases. So it is CFL too.

4)  This is CSL only

Becoz there are two dependent comparisons

5) This is also CSL

Becoz there are two dependent comparisons

6) CFL, CSL but not DCFL

It has only 1 comparison so it is CFL. But now this is not dcfl becoz we dont know when w1 ends and when w2 starts

7) DCFL, CFL, CSL

Now this is DCFL becoz w1 and w2 are separated by # So we know the start and end of w1 and w2

8) CSL

Using stack we cant compare equality of string