toc

Question

L={xww^r |x,w∈(a+b)⁺}

CFL
CSL

none

DCFL

 

Answer 1

I guess, L should be CFL.

L is a concatenation of L1 = {x | x ∈ (a + b)⁺} and L2 = {ww^r | w ∈ (a + b)⁺}.

Here L1 is a regular language, & L2 is a non deterministic CFL.

Since every regular language is context-free, L1 is also a CFL.

& since CFLs are closed under concatenation, L = L1L2 should be a CFL.

Why not a DCFL?

Since L2 is non deterministic CFL so probably it should not be a DCFL.

Comments

You used the word "probably" correctly :)

---

Sir, Actually I was "highly assured"(not Fully)  that L is not a DCFL based on my intuition.

Intuitively I thought that after all in order to accept an string the PDA for L must scan the string completely,

but while scanning since it does not knows at which point it should stop scanning w, & start scanning w^r so there must be Non Determinism present.

What do you think sir, is this idea is enough to assert that L can not be a DCFL here?

PS: If you remember a  few days back,  I had a bad time with my intuition (https://gateoverflow.in/17908/probability). ;)

So I used "probably" there. :D

---

Your answer is correct. And I know why you used "probably" there. If I explain the answer I would also do the same.