Is the following language CFL?

Question

Not able to understand whether it is CFL or not due to the condition 'm>=481'.

Comments

push for a and pop for b . try this for any string

---

here 2 comparison. Can it be done in 1 stack?

---

@srestha ma’am isn’t it regular too?

Like we can have a DFA for 581 m. And then For n=1, we will have 1 path, for n=2 we will have another path and so on till n=581. And then for n=582 we’ll have dead state.

hence regular.

Answer 1

L= {a^n b^m |n<= m & 481<=m}

lets take small version of this language

L= {a^n b^m |n<= m & 1<=m}

then strings in above lang are {b,ab,abb,abbbbb, abbbbb.......}

DPDA for lang is given below.

Comments

It's not Dpda... it's pda.. please correct this

---

On q1 (second state)

q1(b,zo/zo) and q1(€,zo/zo) make violation of Dpda definition...which makes Npda... please read Dpda definition..

Answer 2

Please let me know this DPDA is correct for the above language or not.

I will say this language is DCFL.



 

Answer 3

since a value of m is defined on a certain number which is finite and the comparison of n and m is possible using the stack. So it is CNF