Log In
18 votes

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?

  1. Only $S_1$ is correct
  2. Only $S_2$ is correct
  3. Both $S_1$ and $S_2$ are correct
  4. None of $S_1$ and $S_2$ is correct
in Theory of Computation
edited by

2 Answers

22 votes
Best answer

Only $S_1$ is correct!

A DFA with $3$ states will be needed, as the strings in the language $S_1$ are $00, 0000, 000000,$ and so on. which is the set of all strings with even number of $0's$ and with length greater than $0$. We would have needed only $2$ sates had empty string also been in the language but $n\geq 1$ prohibits it and so we need $3$ states in our DFA. This assumes that the language is over $\{0\}$ and not $\{0,1\}.$

$S_2$ is DCFL as we need to do infinite counting of $0's$ and $1's$ here.

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..
If input Symbol consist of only {0} then only 3 states are enough for S1,if it contains {0,1} then we need 4 states bcz addtion of one dead state.
14 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.

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.

Related questions

21 votes
4 answers
Given an arbitrary non-deterministic finite automaton (NFA) with $N$ states, the maximum number of states in an equivalent minimized DFA at least $N^2$ $2^N$ $2N$ $N!$
asked Sep 14, 2014 in Theory of Computation Kathleen 9.1k views
20 votes
2 answers
Which of the following statements is true? If a language is context free it can always be accepted by a deterministic push-down automaton The union of two context free languages is context free The intersection of two context free languages is a context free The complement of a context free language is a context free
asked Sep 14, 2014 in Theory of Computation Kathleen 8.1k views
16 votes
4 answers
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$
asked Sep 14, 2014 in Theory of Computation Kathleen 3.8k views
26 votes
2 answers
Let a decision problem $X$ be defined as follows: $X$: Given a Turing machine $M$ over $\Sigma$ and any word $w \in \Sigma$, does $M$ loop forever on $w$? You may assume that the halting problem of Turing machine is undecidable but partially decidable. Show that $X$ is undecidable Show that $X$ is not even partially decidable
asked Sep 15, 2014 in Theory of Computation Kathleen 2.4k views