Made Easy Test Series

Question

Why option B is wrong

Comments

Question is not visible

---

Yes, it’s a picture and. I don’t know why but it’s now uploading.

---

Click on “Image”(square box-like icon) →  go to “Upload” tab in “Image Properties” → Browse the file and click on “Send it to the server” → wait →check whether the URL is visible or not in Image Info tab, if visible then click on “OK”.

If the above thing is not working for you then you can send that picture to [email protected] . I’ll attach it here.

Answer 1

Now Consider from you point that option B is correct .

Then the word “abab” belongs to your language where w = ab 

These are the steps that you have preformed on this word

1. on seeing “a” you push it into the stack
2. on seeing “b” you push it into the stack 
3. now after seeing “a” you want to pop from the stack but the “a” that you have pushed in step 1 is at the bottom of the stack there is no way  you can reach the bottom of the stack without removing the top elements of the stack

so ww is not accepted by the automata 

Answer 2

You can try to put w = epsilon, but that only covers one string and leaves many other strings present in language. 

Consider w = ab, then ww = (ab)(ab), so you need to compare first a of first string with first a of second string and so on. To do this, you need to store the first w, we can do this with stack of PDA but there is a problem that stack only accepts LIFO operation, but the a that you want to compare with is present at the bottom of the stack which is not directly accessible. You can’t also throw away the “b” at the top as you need it for further comparison. 

After seeing first w, you need to compare like:

stack:            top       bottom

                       b        a      

           with → a        b

And also this CSL, so PDA won’t be able to accept it for this very reason.

Comments

So, In the q1 state let’s suppose we push ab, as per the example taken by you. Now in the q2, when we pop out in a self-loop, which takes out all the a’s and b’s present. So, We can still accept (ab)(ab).

First push (ab) at q1, then pop (ab) at q2. hence ww, got accepted.

---

The abab is not just about popping, it's about comparing also. The problem will that maybe you can do with this string, but you will also accept some invalid string due to improper comparison. Q2 just says that if TOS = a or b do nothing and self loop.

Now as we are pushing into a stack, the string gets reversed. Example, if the string is w= (abb)(bba), it will be accepted, but technically it should not be.