TOC CFL Language

Question

Check if the following is CFL?

{a^m b^n | (m/n)=10 }

Can we do this with pda?

Answer 1

L={a^m b^n / m=n*10}

When a's come, push one 'a' for every 10 a's. When b's come pop one 'a' for each 'b',.if at the end stack is empty and input is finished accept the language, hence this language is DCFL!

Comments

I will opo one at a time.I can have 10 different states,each doing just pop a.and then coming back to the same state to read next b.Isnt it correct?

---

are you talking about epsilon transitions?

---

Yes.

Answer 2

Yes, it is CFL

{a^m b^n | (m/n)=10 }

We can implement it using PDA. Here, there is only one comparison between variables m and n. It is division that is nothing but subtraction that a PDA can perform using infinite stack.

Comments

yes it is a CFL and there is only one comparison b/w m and n.

---

can we say it is regular as comparisions are finite plzzz correct if am wrong?