search
Log In
16 votes
2.9k views

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?

  1. Only $L1$ and $L2$
  2. Only $L2, L3$ and $L4$
  3. Only $L3$ and $L4$
  4. Only $L3$
in Theory of Computation
edited by
2.9k views

4 Answers

19 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.

edited by
1
As I tis given that set of strings in L3 will be integer....how does it behave for negative numbers?
0
What about negative no  in integers
0
why we can't consider L4 as 0* ?
0
coz $L_4$ will not contain $000$...it only contains exponential number of 0s.
0

@Satbir

Is L4 really a CSL or it should be Recursive Enumerable?

0
it is CSL
0

@satbir

Is this argument correct

Pallindrome, so CSL

I know since its palindrome. Hence, you can use stack but saying that way doesn't seem logically correct.

Don' you think so?

0

Its correct.

all Palindrome strings can be detected with help of 1 stack.

hence it is a CFL

all CFL are CSL

so it should be correct.


Why do you think it is incorrect ?

4 votes

L1 -> This is CSL

L2 -> This is CFL.

L3 -> This is regular. Regular expression (00)*

L4 -> This is CSL.

Answer -> D

1 vote
ans is D. only L3 is regular
0
Plz explain how L3 is regular..?
0 votes

L1, L2 are not Regular because we can't compare strings in Finite Automata. L1 is CSL, L2 is CFL

L3 is Regular because strings generated by L3 are even no of 0's.

L4 is not Regular because we can't design FA.

0
L = w.(w reverse)* | w € {a, b}*?

Please solve this... Is it regular or non regular??
Answer:

Related questions

17 votes
2 answers
1
3.5k views
Consider the following two statements: $S_1: \left\{ 0^{2n} \mid n \geq 1 \right\}$ is a regular language $S_2: \left\{0^m1^n0^{m+n} \mid m \geq 1 \text{ and } n \geq 1 \right\}$ is a regular language Which of the following statement is correct? Only $S_1$ is correct Only $S_2$ is correct Both $S_1$ and $S_2$ are correct None of $S_1$ and $S_2$ is correct
asked Sep 14, 2014 in Theory of Computation Kathleen 3.5k views
15 votes
2 answers
2
1.2k views
Give a deterministic PDA for the language $L=\{a^ncb^{2n} \mid n \geq 1\}$ over the alphabet $\Sigma = \{a,b,c\}$. Specify the acceptance state.
asked Sep 15, 2014 in Theory of Computation Kathleen 1.2k views
37 votes
1 answer
3
4.7k views
Consider the following problem $X$. Given a Turing machine $M$ over the input alphabet $\Sigma$, any state $q$ of $M$ and a word $w \in \Sigma^*$, does the computation of $M$ on $w$ visit the state of $q$? Which of the following statements ... correct? $X$ is decidable $X$ is undecidable but partially decidable $X$ is undecidable and not even partially decidable $X$ is not a decision problem
asked Sep 14, 2014 in Theory of Computation Kathleen 4.7k views
23 votes
2 answers
4
1.7k views
Construct DFA's for the following languages: $L=\left\{w \mid w \in \{a,b\}^*, \text{ w has baab as a substring } \right\}$ $L=\left\{w \mid w \in \{a,b\}^*, \text{ w has an odd number of a's and an odd number of b's } \right\} $
asked Sep 15, 2014 in Theory of Computation Kathleen 1.7k views
...