NCFL,CFL,PDA

Question

 L1={wlwR∣w∈{a,b}∗,l∈{a,b} }

which type of language is this DCFL or NDCFL? (note that l∈{a,b} not {a,b}*)

I feel its NDCFL can you also tell how PDA will look like?

Answer 1

Yeah this is not only DCFL but also regular. So, FSA is enough. It has to accept the regex of the form 

a(a+b)^*a+b(a+b)^*b + a + b

Comments

Its PDA

---

How? A regex can be accepted by a FSA right?

---

See below. Sourabh has given explanation.

Answer 2

no it will be ncfl ryt? . because for w supppose it will be  aaab than l can be any (a+b) so here we can't do the work determiniatically so it will be cfl but not dcfl

Comments

@Sushant , I have edited my comment, this NFA doesnot accept ab, but accepts strings with same starting and ending letters and accepts (a+b).

Can you check it?

---

@Nithish.

abaaa is accepted by your NFA but not by def. of language. I made the same mistake.

Observe closely.

---

@Sushant, Got it. My bad. Wasted lot of time. This can be accepted by NPDA only.