Question

Assume the power of a string w over the concatenation operation (.) as follos:
$w^0=ϵ$
$w^{\prime +1}-w^{\prime }.w$
$\text{The number of states in the minimal DFA (over the unary alphabet {1}) of the language corresponding to the regulare expression}(1^3+1^{2013}{)}^{\ast }+(1^6+1^{2022}{)}^{\ast }\text{is equal to \_\_\_\_\_\_.}$

Answer 1

$\text{The regular expression is}(1^3+1^{2013}{)}^{\ast }+(1^6+1^{2022}{)}^{\ast }$
$=(1^3{)}^{\ast }+(1^6{)}^{\ast }$
$=(111{)}^{\ast }+(111111{)}^{\ast }=\left(111\right)$


Hence,only 3 states is required.