NPTEL Assignment Question

Question

A regular expression for accepting strings with exactly one $1$ more than $0$’s is

• A. $0^{\ast}1$
• B. $(0|1)^{\ast}1(0|1)^{\ast}$
• C. $(0|1)^{\ast}1(0|1)^{\ast}|1(0|1)^{\ast}$
• D. Not possible

Comments

Question is not clear.

---

A) 01 generate which is wrong

B) 100 generate which is wrong

C) 100 generate which is wrong

So the answer is d.

Actually, there is a comparison between 0’s and 1’s. Therefore L is not Regular.

Language is CFL.

S → 1A | A1

A → 1A0 | 0A1 | $\epsilon$

:)

---

@Yaman explain the question

---

The question says exactly one 1’s more than 0’s

Total 1’s in string = Total 0’s in string + 1

---

thanks

---

D)

Reason:- Here, we need to store the number of 0’s appeared so that we can add 1’s 1 more than number of 0’s appeared. We do not have memory in DFA and NFA.

Answer 1

The condition is there should be one 1 more than 0 in the language. So, the language of the strings would be:

{1,011,110,101,00111,….}

Now lets see each option:

1. 0*1:  Here, * can produce any number of 0’s ie 001 will also be generated by this regex which is not part of our language – False
2. (0+1)*1(0+1)*: Here, we can have strings like 010 which is not the part of our language – False
3. (0+1)*1(0+1)* + 1(0+1)*- Here also we can have strings like 010, 100,… -False

Hence, answer should be option D.

Also, 

We can think as for generating this language, we would need to remember the number of 0’s which needs memory. So, cannot be done by a dfa. We need a PDA for it

Hence, option D