GATE CSE 2001 | Question: 1.4

Question

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?

• A. Only $S_1$ is correct
• B. Only $S_2$ is correct
• C. Both $S_1$ and $S_2$ are correct
• D. None of $S_1$ and $S_2$ is correct

Comments

my logic is
Statement 1: there is no need of counting so ii is counting

statement 2 : is wrong because we need to count m+n in 0

Answer 1

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.

Comments

s1 is dfa with 4 states bcoz it is given in question that n>=1.so 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'..to 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.

Answer 2

DFA For S₁ :

S₂ 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.

Comments

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.

Answer 3

Please see pdf explanation that answers S2 using pumping lemma.