# 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 ...
• 3,956

### 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 ...
• 143

### Proving Equivalence of Two Regular Expressions

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 ...
• 1,005
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$ ...