TIFR CSE 2012 | Part B | Question: 18

Question

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?

• A. Both $L_{1}$ and $L_{2}$ are context-free languages.
• B. $L_{1}$ is context-free and $L_{2}$ is recursive but not context-free.
• C. Both $L_{1}$ and $L_{2}$ are recursive but not context-free.
• D. $L_{1}$ is regular and $L_{2}$ is context-free.
• E. Complement of $L_{2}$ is context-free.

Answer 1

$L_1$ - CFL, $S \rightarrow aSbb \mid abb$

$L_2$ - Not CFL ,we can't count $i^2$ using CFL.

1. False because $L_2$ is not CFL.
2. True. $L_2$ is recursive
3. False because $L_1$ is CFL.
4. False, $L_1$ not regular.
5. 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.

Comments

L2  is CSL or RECURSIVE  ???

---

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 ?

---

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. :)

Answer 2

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

Answer 3

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. 

Comments

How can it checks the square property ??