DOUBT

Question

my answer is "B" but the answer is given "C"

Comments

for second one u have to go in 2 states on seeing a..one for checking exact no of bs and other for twice no of bs...

---

Can u pls draw state diagram of it ?

---

can u draw a pda for aⁿbⁿc?
 

Answer 1

The answer given is correct..Let us see how :

For 1st one :

a) Firstly there is clear piece of determinism how much to pop according to first input..

b) If the first input is 'c' , then we push a's into the stack , then as soon as 'b' comes into stack , then we start popping 'a' from the stack for every 'b' that is read in input..

c) If the first input is 'd' , then we push a's into the stack , then when b's come into input , so for every 2 b's read from the input , we pop 1 'a' from the stack..

So there is clearly determinism in writing the rules..Hence L1 is DCFL..[Might get trapped if one uses closure property as DCFLs are not closed under union ]

For 2nd one : 

Here there is an issue because 'a' comes in the input in the beginning and we need comparison..So we use stack to push 'a' into stack..But as soon as 'b' comes we do not know at that moment whether to go for aⁿ bⁿ or aⁿ b²ⁿ..

Hence the second one is NCFL.

Hence C) is correct answer..

Comments

Can u pls tell how L2 is implemented ? (using push / pop) or using PDA diagram

---

thnx @Hbibkhan :)

Answer 2

c) is correct answer 

for l1 it will be done by deterministic pda so dcfl 

L2 will be ncfl 

hence c) option answer .

Comments

Check my answer @kunal chalotra..It is a tricky question..:)

---

yes habib u r correct .  :) i made a mistake thanks for rectifying it

---

@kunal chalotra cube solver will kill you ...don't do mistake :)

---

k @Debashish i will take care , next time :)

Answer 3

L1 is  DCFL as when we start reading the input, on the dirst instance only we can determine whether we would need to pop an a for a b or pop an a for two b's. Therefore there is determinism.

In L2 We cannot determine whether we would pop for single b or double b's therefore there will exists a state for which there will be two transitions. Therefore Non deterministic.