The Gateway to Computer Science Excellence
0 votes

The operation of Problem $4.2.3$ is sometimes viewed as a $"$derivative and $a/L$ is written $\frac{dL}{da}.$ These derivatives apply to regular expressions in a manner similar to the way ordinary derivatives apply to arithmetic expressions. Thus if $R$ is a regular expression, we shall use $\frac{dR}{da}$ to mean the same as $\frac{dL}{da},$if $L=L(R).$

  1. Show that $\frac{d(R+S)}{da}=\frac{dR}{da}+\frac{dS}{da}$
  2. Give the rule for the $"$derivative$"$ of $RS.$ Hint$:$ You need to consider two cases$:$ if $L(R)$ does or does not contain $\in.$ This rule is not quite the same as the $"$product rule$"$ for ordinary derivatives, but is similar.
  3. Give the rule for the $"$derivative$"$ of a closure, i.e.,$\frac{d(R^{*})}{da}$
  4. Use the rules from $(a)-(c)$ to find the $"$derivatives of regular expression $(0+1)^{*}011$ with respect to $$0 and $1.$
  5. Characterize those languages $L$ for which $\frac{dL}{d0}=\phi$
  6. Characterize those languages $L$ for which $\frac{dL}{d0}=L$
in Theory of Computation by Veteran (59.5k points)
edited by | 10 views

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,406 answers
105,468 users