4
$\begingroup$

so I am currently learning about dfa and nfa and i came across the following question which requires me to use Brzozowski's derivatives method to construct a minimal DFA recognizing the language defined by the rational expression below. I am having quite a bit of trouble understanding how Brzozowski's derivatives works and how I would apply it to the expression below. Could someone please show me step by step how I would do it alongside and explanation.

What seems to be the main problem is that I am not sure how to derive the derivative such as dR/da.

X = (aa + b)* ab (bb)*
$\endgroup$
4
$\begingroup$

The Brzozowski derivative of a language $L$ with respect to a symbol $a$ consists of all words $w$ such that $aw \in L$.

In your case, $L$ is the language generated by the regular expression $X$. Instead of solving your exact exercise, I will show how to compute the other Brzozowski derivative, with respect to $b$. A word generated by $(aa+b)^*ab(bb)^*$ has the form $$ x_1 \ldots x_n ab (bb)^{2m}, $$ where $n \geq 0$, $x_i \in \{aa,b\}$, and $m \geq 0$. The only way that this can start with $b$ is if $n \geq 1$ and $x_1 = b$. Taking away $b$, we are left with $$ x_2 \ldots x_n an (bb)^{2m}, $$ a collection of words which is described by the regular expression $(aa+b)^*ab(bb)^*$, the same one we started with.

Computing the derivative with respect to $a$ is slightly more complicated since there are two different cases, but I'll leave you to ponder that.

You might have also learned some rules for computing the derivative. In that case, you can compute the derivative by applying them mechanically.

$\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.