New answers tagged

0 votes

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 ...
user avatar
2 votes

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 ...
user avatar
4 votes

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 ...
user avatar
  • 143
0 votes

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 ...
user avatar
31 votes
Accepted

Proving Equivalence of Two Regular Expressions

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$ ...
user avatar

Top 50 recent answers are included