TOC Query

Question

For $S \rightarrow 0S1 | \epsilon$ for $\sum=\{0,1\}^*$, which of the following is wrong for the language produced?

(a) Non regular language

(b) $0^n1^n | n\geq0$

(c) $0^n1^n | n\geq1$

(d) None of the mentioned

Comments

$\text{C}$ is incorrect because it can’t produce $\epsilon$

Answer 1

Answer: C

Options A and B are correct.

 

Explanation:

A: For the given language that generates epsilon or an equal number of zeros followed by an equal number of ones, we cannot design finite automata as the count of the variables cannot be accounted for. So, PDA would do the job. Therefore, the language is non-regular.

B: At n=0 generates epsilon and at n=1,2..so on generates an equal number of zeros followed by an equal number of ones. Therefore satisfy the given language.

C: Here the epsilon cannot be generated.