theory of computation

Question

The Language is given by,

L is a 

A) Deterministic CFL.

B) Non deterministic CFL but not DCFL.

Please draw the PDA for the above language ...

Answer 1

It,s not a CFL. Because in language $ L = \{ w : 2 n_a (w) <= n_b (w) <= 3 n_c (w) \} $, There are two conditions, $ 2 n_a (w) <= n_b (w) $ and $ n_b (w) <= 3 n_c (w) $, which you can not satisfy with one stack. Hence Its not possible to draw PDA.

Comments

in peter linz it is given as NPDA 

---

See @ Vignesh

here smallest language can be aabccc

So, how could u compare No of a,b,c at the same time?

So, PDA cannot be drawn by this

---

@Vignesh, First this, as I can see that it's has asked to create NPDA, but it has not claimed that all the below language, is CFL. If NPDA does not exist then you can write in answer that, NPDA does not exist for this language.

As Once, my TOC teacher has given lots of languages to create the FA, as homework, and the last language was $ L = \{ a^n b^n | n >= 1\} $,Today we all know that it's not possible to create FA for the language, but all the students created something, and claims they are right. The next day asks everyone in front and asks them to draw there solution on the board, and he start giving contradicting strings, that see this string should not be accepted and here your FA is accepting this. kind of. Later he explain the reason and we move to PDA.

May be, Linz also has done same things.

Second, It can not be possible with only one stack, hence its not at all CFL. Hence impossible to create NPDA.