0
$\begingroup$

Assume a language like $L=\{w:(n_a(w)-n_b(w))mod3=1\}$ is given.
How can i find a regular expression for this language using a systematic process?
Note : I can easily draw a DFA accepting this language with 3 states. ( The remainder can be either 0 or 1 or 2. ) But the problem is how to find the regular expression.

$\endgroup$
1
$\begingroup$

The state removal method is probably the simplest to do by hand. In this example, we need only remove one state, $2$. Afterward, the edge $0\to1$ will be labeled $a\mid bb$, the edge $1\to0$ will be labeled $b\mid aa$, and we add loops $0\to 0$ labeled $(ba)^*$ and $1\to1$ labeled $(ab)^*$. The resulting regular expression is $$(ba)^*(a\mid bb)((ab)^*\mid(b\mid aa)(ba)^*(a\mid bb))^*. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.