1 votes 1 votes The language $L=\{a^n b^n a^m b^m \mid n \geq 0, m \geq 0 \}$ is Context free but not linear Context free and linear Not context free and not linear Not context free but linear Theory of Computation ugcnetcse-sep2013-paper3 theory-of-computation identify-class-language + – go_editor asked Jul 22, 2016 recategorized Oct 19, 2018 by Pooja Khatri go_editor 2.7k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 1 votes 1 votes Answer A A linear grammar can express an bn but not an bn am bm. Because such a language must need more than one non terminal at right side L is not linear L is context free. Push each a in input in a stack. When b encounters in input, pop one element from stack, When all bs are processed and next a comes if stack is empty a m b m is satisfied Similar approach can be used to check a n b n Hence L is context free sh!va answered Jul 22, 2016 selected Dec 25, 2016 by Arjun sh!va comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments ManojK commented Jul 22, 2016 reply Follow Share I think grammar will be $S\rightarrow AA \\ A\rightarrow aAb \\ A\rightarrow \epsilon$ which is not linear. 1 votes 1 votes ManojK commented Jul 22, 2016 reply Follow Share Also edit the first line .//need not necessary 0 votes 0 votes sh!va commented Jul 22, 2016 reply Follow Share Okay sir.. 0 votes 0 votes Please log in or register to add a comment.