DCFL - TOC

Question

Is the following language a DCFL? Please explain your reasoning.

Comments

my thinking:

We can design a DPDA that pops ‘a’ for every ‘b’ and pops both ‘b’ and ‘a’ for every ‘c’. In the end we’ll have an empty stack and the string will be accepted if it’s in the language. Hence, it’s a DCFL.

Is my logic correct?

---

@atulcse Let’s check your logic

Let m = 2, n=3 and p=4

L = {$a^5 b^7 c^6$}

First all the a’s has been push onto the stack then for every b, a is popped

Now there will be 2 b’s and no a’s onto the stack and #c = 6. How will you match that?

 

---

I see, we can't match in that case. Thanks for the example

---

CFL not DCFL.

---

Language is CFL but not DCFL

---

What is the CFG for this language? If it is CFL.

Answer 1

it is CFL language  here pop and push not determinsitic

let us suppose you pushing all a in stack after that b become then how you decide  how many b    a pop  and remaining of b push in stack  to compare with c so here nondetermenism exist so it is cfl not dcfl

Answer 2

it is CFL language  here pop and push not determinsitic

let us suppose you pushing all a in stack after that b become then how you decide  how many b    a pop  and remaining of b push in stack  to compare with c so here nondetermenism exist so it is cfl not dcfl