The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+9 votes

Consider the following two statements:

$S1: \left\{ 0^{2n} \mid n \geq 1 \right\}$ is a regular language

$S2: \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?

  1. Only S1 is correct
  2. Only S2 is correct
  3. Both S1 and S2 are correct
  4. None of S1 and S2 is correct
asked in Theory of Computation by Veteran (68.8k points)
edited by | 773 views

2 Answers

+14 votes
Best answer
Only s1 is correct!
A DFA with 3 states will be needed, as the strings in the language S1 are $00, 0000, 000000,$ and so on..

S2 is DCFL.
answered by Veteran (14k points)
edited by
i think both are false

if df has 2 states and one of the state is initial and final then it would accept empty string too which is not part of the language as n>=1 if incase n>=o then it would be regular

Can you explain me why S2 is not regular. it is 0^2m 1^2n , we can construct regular language fr 0^ 2m and same for 1^2n and unioin them. m and n are not dependent
@Divya Bharti

Read the question carefully

S2 is not 02m 12n

S2:{0m1n0m+n∣m≥1 and n≥1}

S2 is not regular because last 0 is dependent on value of m and n
got it :) thanks
s1 is dfa with 4 states bcoz it is given in question that n> yes it will be regular.
and s2 is context free language.

option A) is correct.
S1 can't be accepted with 2 states dfa since min string is '00' accept it we require min 3 state dfa..

if it would be n>=0, then 2 state dfa needed..
+11 votes

DFA For S1 :

S2 is PDA since stack is needed for comparision finite memory is not sufficient

              Till 1 push in stack after that pop from stack for every 0.

answered by Veteran (57.5k points)
I have a question is S2 dcfl or not?
According to me it is
According 2 me
We can push 0 and 1 on the stack and then pop 1's and 0's
Plz do correct me if i m wrong
YES push till all 1's when 0 come after all 1's start poping all elements.
3 states are enough for S1.

Hi @sourav ji, Thank You.

I think this answer is corrected. 


If you assume you have only 0 then selected answer is correct.

In that case also, I think we can not do in 2 states. Min 3 states are required because n>=1.


$\text{And why do you think so ?}$Chhotu

Chhotu  $\text{both selected as well as non selected answer are correct}$

Actually the question itself is little bit unclear because set of possible input symbols are not given.

  • If you assume you have only $0$ then selected answer is correct.
  • If you assume you have  $0,1$ then Prashant's answer is correct.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

32,470 questions
39,199 answers
36,575 users