2 votes 2 votes Check if the following is CFL? {a^m b^n | (m/n)=10 } Can we do this with pda? Theory of Computation theory-of-computation context-free-language + – rahul sharma 5 asked Jul 31, 2017 • retagged Oct 13, 2017 by Arjun rahul sharma 5 780 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
2 votes 2 votes 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! Manu Thakur answered Jul 31, 2017 • edited Jul 31, 2017 Manu Thakur comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments rahul sharma 5 commented Jul 31, 2017 reply Follow Share 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? 0 votes 0 votes Manu Thakur commented Jul 31, 2017 reply Follow Share are you talking about epsilon transitions? 0 votes 0 votes rahul sharma 5 commented Jul 31, 2017 reply Follow Share Yes. 0 votes 0 votes Please log in or register to add a comment.
–1 votes –1 votes 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. Raushank2 answered Jul 31, 2017 Raushank2 comment Share Follow See all 2 Comments See all 2 2 Comments reply shivam patidar 1 commented Jul 31, 2017 reply Follow Share yes it is a CFL and there is only one comparison b/w m and n. 0 votes 0 votes Kaluti commented Aug 4, 2017 reply Follow Share can we say it is regular as comparisions are finite plzzz correct if am wrong? 0 votes 0 votes Please log in or register to add a comment.