0 votes 0 votes 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 ... Theory of Computation theory-of-computation + – Vicky rix asked Apr 12, 2017 • retagged Jun 4, 2017 by Arjun Vicky rix 641 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 4 votes 4 votes 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. rude answered Apr 12, 2017 • selected Apr 12, 2017 by Vicky rix rude comment Share Follow See all 3 Comments See all 3 3 Comments reply Vicky rix commented Apr 12, 2017 reply Follow Share in peter linz it is given as NPDA 0 votes 0 votes srestha commented Apr 12, 2017 reply Follow Share 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 1 votes 1 votes rude commented Apr 12, 2017 reply Follow Share @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. 1 votes 1 votes Please log in or register to add a comment.