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?
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.
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.
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.
64.3k questions
77.9k answers
244k comments
80.0k users