MADE EASY TEST SERIES

Question

Is L = {a bⁿ aⁿ ;n > 0} $\cup${aa b^k a^2k ;k > 0} a DCFL ???

Comments

yes it is DCFL

---

Could you please explain your answer.

Answer 1

L = {a bⁿ aⁿ ;n > 0} ∪∪{aa b^k a^2k ;k > 0}.

---

DCF Grammar  for generating above language ->

S -> aT

T - > aU | bV

U - > bUaa | baa

V  - > bVa | a

---

 DPDA for accepting above language  -> 

Comments

@vijay @Kapil

Both part are DCFL.

DCFL not closed under union.

So, result may or may not be DCFL.

Now, it is starting with DCFL format.

But at end can we confirm it is DCFL?

Say,

S->aSbb | aSbbb |$\epsilon$

is it DCFL?

---

@srestha, Here in this particular case it seems like it is union of 2 DCFL, but it is not so... you can check above DCFG and DPDA, ... if you find any problem in that then please let me know...  

Now coming to your exampe -

S -> aSbb | aSbbb | ϵ

L = aⁿb^m  , where n >0 ,    2n=<m <= 3m.

rt  ??

And I think, it is not even CFL right ??

Can we implement an PDA with 1 stack ?? I don't think we can ...

---

in the above given implementation for an a we will either push 2 b's or 3 b's then why it cannot be an ncfl.