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)*
Improve this question
$\endgroup$

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
0
$\begingroup$

can anybody help me on this

From the definition above also know that . Provide the simplified expressions [R]D ε = R for the following derivatives of : 0 ) 1R = ( +1 * A. [R] D1 B. [R] D10 C. [R] D11

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics. You can use LaTeX. $\endgroup$
    – D.W. ♦
    Commented Apr 17, 2020 at 18:37
  • $\begingroup$ Please give proper attribution to all copied material: cs.stackexchange.com/help/referencing. We discourage answers that consist solely or primarily of copied material, even if you provide credit. $\endgroup$
    – D.W. ♦
    Commented Apr 17, 2020 at 18:37
  • 1
    $\begingroup$ I can't understand your sentences. "also know that" seems missing some words. I don't know what you mean by "Provide the simplified expressions.." - are you trying to ask a new question? Something seems to have gone wrong with the formatting of your last sentences. Perhaps you tried to copy-paste, but the formatting did not come through. $\endgroup$
    – D.W. ♦
    Commented Apr 17, 2020 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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