As I tis given that set of strings in L3 will be integer....how does it behave for negative numbers?

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+13 votes

Consider the following languages:

- $L1=\left\{ww \mid w \in \{a,b\}^*\right\}$
- $L2=\left\{ww^R \mid w \in \{a,b\}^*, w^R \text{ is the reverse of w} \right\}$
- $L3=\left\{0^{2i} \mid \text{ i is an integer} \right\}$
- $L4= \left\{ 0^{i^2} \mid \text{ i is an integer} \right\}$

Which of the languages are regular?

- Only $L1$ and $L2$
- Only $L2, L3$ and $L4$
- Only $L3$ and $L4$
- Only $L3$

+16 votes

Best answer

$L1=\{ww \mid w \in \{a,b\}^*\}\qquad$CSL

$L2=\{ww^R \mid w \in \{a,b\}^*,w^R \text{ is the reverse of w}\}\qquad$Palindrome, so CFL

$L3=\{0^{2i} \mid i \text{ is an integer}\}\qquad$Linear power and regular expression can be stated as $(00)^*$

$L4=\{0^{i^2} \mid i \text{ is an integer}\}\qquad$Non-linear power, so CSL

Therefore, answer is option D.

$L2=\{ww^R \mid w \in \{a,b\}^*,w^R \text{ is the reverse of w}\}\qquad$Palindrome, so CFL

$L3=\{0^{2i} \mid i \text{ is an integer}\}\qquad$Linear power and regular expression can be stated as $(00)^*$

$L4=\{0^{i^2} \mid i \text{ is an integer}\}\qquad$Non-linear power, so CSL

Therefore, answer is option D.

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 6.9k
- Digital Logic 2.7k
- Programming & DS 4.8k
- Algorithms 4.1k
- Theory of Computation 5.2k
- Compiler Design 2k
- Databases 3.9k
- CO & Architecture 3.4k
- Computer Networks 3.9k
- Non GATE 1.4k
- Others 1.5k
- Admissions 514
- Exam Queries 525
- Tier 1 Placement Questions 23
- Job Queries 67
- Projects 18

46,786 questions

51,234 answers

176,575 comments

66,585 users