# Tag Info

### How to evaluate the tightness of a bound on a function?

To evaluate tightness of a bound on a function, you need to find both the upper and lower bounds. Finding an upper bound on the function is good but it leaves the possibility that the actual function ...

### Proving Equivalence of Two Regular Expressions

If you generate a minimal DFA from a regular expression, then you can label each state uniquely with the lexically smallest string that reaches the state. This makes it very easy to check for ...

### Proving Equivalence of Two Regular Expressions

If you wanted to prove this extra formally, you could try to prove this in a proof assistant, such as Lean (or Coq or Agda or ...). Here's how you can state that problem using Lean's ...
It appears it should be possible to show the regular expressions $r_1=(1+01)^*$ and $r_2=(1^* 011^*)^*+1^*$ generate the same language, by showing that each string generated by $r_1$ can also be ...
One way to prove that two regular expressions $r_1,r_2$ generate the same language is to show both inclusions: Show that if $w$ is generated by $r_1$ then it is generated by $r_2$. Show that if $w$ ...