DFA that accepts strings where there are odd number of 1's, and any number of 0's

Question

DFA that accepts strings where there are odd number of 1's, and any number of 0's.

The alphabet $\Sigma=\{0,1\}$

Well since it's odd $1$'s, then there must be at least one 1.

So I think the regex is the following:

$$R=0^*10^*$$

This is correct because I can have any number of $0's$, but also incorrect because I do not offer a way to add more 1's. How do I modify this $R$ so that I can have $3,5,7,\dots$ ones?

Answer 1

I hope it can help you

DFA that accepts strings having an odd number of $1$'s: There are several methods for reading a regular expression from a DFA. If we use the state removal technique:

this DFA are in Final form , regular expression for DFA is : $0^*1(0+1{0}^*1)^*$

---

Brzozowski Algebraic Method using Arden's Theorem

Note that when we apply Arden's theorem, the transition graph does not have $\epsilon-moves$ and it should have only one initial state, say $N_1$.

1. its vertices are $N_1,N_2,....N_n.$
2. $N_i$ is the regular expression representing the set of strings accepted by the system even though $V_i$ is finial state.
3. $\alpha_{ij}$ denotes the regular expression representing the set of labels of edges from $N_i$ to $N_j$,when there is no such edge, $\alpha_{ij}=\emptyset$

consequently, we can get the set of equations.here $\epsilon$ should be added in the equation of initial state $N_1$, i.e.

\begin{align} &N_1=N_1\alpha_{11}+N_2\alpha_{21}+ ... +N_n\alpha_{n1}+\epsilon \\ &N_2=N_1\alpha_{12}+N_2\alpha_{22}+ ... +N_n\alpha_{n2} \\ .\\ .\\ .\\ &N_n=N_1\alpha_{1n}+N_2\alpha_{2n}+ ... +N_n\alpha_{nn} \\ \end{align}

by repeatedly applying substitution and Arden's theorem, we get $N_i$ in terms of $\alpha_{ij}$'s.if there are more final states,then we have to take the union of all $N_i$'s corresponding to the final states.

---

"Introduction to Automata and Compiler Design - Dasaradh Ramaiah K."

If we use the Brzozowski Algebraic Method: \begin{align} &q_0=q_00+q_11+\epsilon \\ &q_1=q_01+q_10 \end{align}

by Arden's theorem ($r=rp+q$ has only solution $r=qp^*$) for $q_1$ we have: \begin{align} &q_1=q_010^* \tag{1} \end{align}

---

\begin{align} &q_0=q_00+q_010^*1+\epsilon \\ &\,\,\,\,\,=q_0(0+10^*1)+\epsilon \end{align} by Arden's theorem for $q_0$ we have:

\begin{align} &q_0=(0+10^*1)^* \tag{2} \end{align}

final regular expression is: $$(0+1{0}^*1)^*10^* \tag{1,2}$$

Answer 2

So after the first 1, you want any other 1s to come in pairs. $0^*10^*10^*$ gives you a pair of 1s, $(0^*10^*10^*)^*$ gives you any number of pairs of 1s, so $$0^*10^*(0^*10^*10^*)^*$$ should do the trick.