doubt

Question

i am not able to solve length matching problem.so plz explain how to solve this type of problem: 

1.    { W1 # W2 # W3 /  |W1| =| W2| & |W1| = |W3| }

2.     { W1 # W2 # W3 /  |W1| =| W2| or  |W1| = |W3| }  

3.     { W1 # W2 W3 / W2= W1^R }

plz explain and tell a method:

Answer 1

For such questions it is always preferable to verify the fact that whether we are able to simulate the language using a DPDA or PDA as the case may be or not..

So let us take first example :

L1  = { w1 # w2 # w3  |  |w1| = |w2| = |w3| }..

Since there is a '#' in between each of w1 and w2 , compulsorily we need to use stack for length matching purpose..

So now we push the contents of |w1| into stack whatever it is..Then when '#' comes in the input , then we transit to other state in the machine..Then as we read the contents of w2 , then w1's contents are popped out of stack..

Then '#' comes and also the stack is empty..Now we have nothing to compare  with for the length of w3 as the stack has become empty..

So the given language is not even CFL..

This is a CSL in fact as it can be implemented by LBA(Linear Bounded Automata)

Now the second language is slightly different ..Let us describe what is the difference :

Here we have 2 scenarios , a) |w1| = |w2| ..For this we do stack implementation as described earlier..

                                        b) |w1| = |w3| ..For this also we can do the same ..

But the thing is for this , say if we follow (a) , then we need not care about |w3| and if we follow (b) , we need not care about |w2|..In other words , non determinism has come into picture as which one of the 2 choices to consider..

Hence it is a CFL but not DCFL..

Now the 3rd language L = { w1 . # . w1^R . w3 } is a DCFL..Let us see how..

We push the contents of w1 into the stack while reading them from input tape..Then as soon as '#' is read from input , do the state transition and nothing else..Now for each symbol of w1^R we compare with top of stack and on match we pop from the stack and continue the process in the same manner till w1^R  is completed..

Now after that w3 can be anything so we need not bother about that..

Hence we have clear decision as when to do what ..

Hence it is a DCFL..

Hope this helps resolving your doubt..

Comments

thks bro ...and what about  this  1.   {W1 # W2 # W3 / W2 =W1 }   

                                                   2. { w1 w2 / | w1 | =  |w2| }

these two explain??

---

1. {W1 # W2 # W3 / W2 =W1 }

  w # w is csl since minimum 2 stack is needed. so Whole language is CSL .

like w= 111 then language 111 # 111

so a11 # a11

    aa1 # aa1

    aaa # aaa hence accepted

2.  { w1 w2 / | w1 | =  |w2| }

is regular   ie. every even length string is accepted.

---

The first one is a CSL..

And second one is regular..

---

@habib plz explain first one

---

@aniruth  habib says first one DCFL plz clear its CSL or DCFL