13 votes 13 votes Let $a^{i}$ denote a sequence $a . a ... a$ with $i$ letters and let $\aleph$ be the set of natural numbers ${ 1, 2,...}$. Let $L_{1}=\left\{a^{i}b^{2i}\mid i \in \aleph\right\}$ and $L_{2}=\left\{a^{i}b^{i^{2}}\mid i \in \aleph\right\}$ be two languages. Which of the following is correct? Both $L_{1}$ and $L_{2}$ are context-free languages. $L_{1}$ is context-free and $L_{2}$ is recursive but not context-free. Both $L_{1}$ and $L_{2}$ are recursive but not context-free. $L_{1}$ is regular and $L_{2}$ is context-free. Complement of $L_{2}$ is context-free. Theory of Computation tifr2012 theory-of-computation identify-class-language + – makhdoom ghaya asked Nov 2, 2015 edited May 15, 2018 by Milicevic3306 makhdoom ghaya 1.5k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 14 votes 14 votes $L_1$ - CFL, $S \rightarrow aSbb \mid abb$ $L_2$ - Not CFL ,we can't count $i^2$ using CFL. False because $L_2$ is not CFL. True. $L_2$ is recursive False because $L_1$ is CFL. False, $L_1$ not regular. False, as complement of $L_2$ is also not context free. It still need to computer $i^2$ for checking for inequality. Answer is B. Akash Kanase answered Nov 15, 2015 edited Jun 15, 2018 by Milicevic3306 Akash Kanase comment Share Follow See all 3 Comments See all 3 3 Comments reply itsvkp1 commented Aug 31, 2017 reply Follow Share L2 is CSL or RECURSIVE ??? 0 votes 0 votes David commented Apr 1, 2018 reply Follow Share how do we conclude that the language is recursive ... ? If an algorithm that can be implemented in a computer can be designed , then the language is recursive ? 1 votes 1 votes rohith1001 commented Sep 19, 2019 reply Follow Share I guess L2 is a CSL. L2 can be accepted by a Linear bouned Automata. The tape size is allowed to be a function of the input string. So, even if we have a limited string LBA can accept L2. Please correct me if I'm wrong. :) 1 votes 1 votes Please log in or register to add a comment.
3 votes 3 votes L1={ab,aabbbb,aaabbbbbb,...........} so, it can be written like aSbb, It is CFL L2={ab,aabbbb,aaabbbbbbbb............} it cannot be a CFL so ans is b srestha answered Nov 2, 2015 srestha comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes Option b L1 have linear power and only one comparison between a and b so it is CFL. L2 is not in linear power so it is CSL. and hence recursive. abhishekmehta4u answered Apr 1, 2018 abhishekmehta4u comment Share Follow See 1 comment See all 1 1 comment reply mrinmoyh commented Sep 17, 2019 reply Follow Share How can it checks the square property ?? 0 votes 0 votes Please log in or register to add a comment.