<p>I will give this a go, so that next time somebody is Googling it they can find it . I will try to make this educational and use Haskell, as the question suggests.</p>
<hr />
<p>Let us first define a data type for regular expressions. Notice the difference between <code>Epsilon</code> (commonly noted as <span class="math-container">$\lambda$</span> or <span class="math-container">$\epsilon$</span>), which matches the empty string, and <code>Null</code> (sometimes noted as <span class="math-container">$\emptyset$</span>, but not found commonly in the definition of regular expressions), which does not match any string, i.e., it generates the empty language.</p>
<pre><code>data RE = Null | Epsilon | Symbol Char | Union RE RE | Concat RE RE | Star RE
  deriving (Eq, Show, Generic)
</code></pre>
<p>Let us also define a function that produces the language generated by a regular expression. This function produces a (possibly infinite) list of strings, which does not necessarily contain unique elements.</p>
<pre><code>gen :: RE -&gt; [[Char]]
gen Null = []
gen Epsilon = [[]]
gen (Symbol c) = [[c]]
gen (Union r1 r2) = gen r1 ++ gen r2
gen (Concat r1 r2) | null l1 || null l2 = []
                   | otherwise = [s1 ++ s2 | s1 &lt;- l1, s2 &lt;- l2]
  where l1 = gen r1
        l2 = gen r2
gen (Star r) = l
  where l = [] : [s ++ s_star | s &lt;- gen r, s /= [], s_star &lt;- l]
</code></pre>
<p>The definition of <code>gen</code> is straightforward except for two points:</p>
<ul>
<li>In concatenation, the second rule would suffice mathematically. However, if <code>r1</code> generates an infinite language and <code>r2</code> generates an empty language, the list comprehension would give an infinite loop. We solve this by bailing out immediately, in the case of empty languages.</li>
<li>In Kleene's star, we generate the empty string up front, then we exclude empty strings from the language generated by <code>r</code>. Without this, the list comprehension would be stuck producing an infinite list of empty strings.</li>
</ul>
<p>Then, we define the equivalence of regular expressions. Mathematically, <code>r1</code> is equivalent to <code>r2</code> iff the language <code>gen r1</code> is equal to the language <code>gen r2</code>. However, in Haskell, these languages are represented by infinite lists of strings and checking for their equality would be problematic because of three reasons:</p>
<ul>
<li>strings in the list may occur multiple times,</li>
<li>the order of strings in the list is important, and</li>
<li>checking the equality of two equal infinite lists takes infinite time.</li>
</ul>
<p>We will therefore make a simplification, which suffices for the purpose of what we're trying to show here. We define <code>gen'</code> by taking the list that consists of the first 100 strings generated by <code>gen</code>, sorting them and excluding duplicate elements. Then we define regular expression equivalence by comparing the results of <code>gen'</code>.</p>
<pre><code>import Data.List

gen' :: RE -&gt; [[Char]]
gen' = nub . sort . take 100 . gen

equivalent :: RE -&gt; RE -&gt; Bool
equivalent r1 r2 = gen' r1 == gen' r2
</code></pre>
<p>Notice that, strictly speaking, this definition of equivalence is mathematically wrong. As I said, however, it suffices for what we're trying to do here, as we are only interested in equivalence with <code>Null</code> and <code>Epsilon</code>, whose languages are finite and contain 0 and 1 elements, respectively.</p>
<p>Then, we will use <a href="https://hackage.haskell.org/package/QuickCheck/docs/Test-QuickCheck.html" rel="nofollow noreferrer">QuickCheck</a> for proving (or disproving) that the definitions for <code>nullRE</code> and <code>epsRe</code> are correct. QuickCheck is the seminal library for property-based testing. We will need the following lines in our preamble:</p>
<pre><code>{-# LANGUAGE DeriveGeneric #-}
import Generic.Random
import GHC.Generics

import Test.QuickCheck
</code></pre>
<p>as well as the following, for generating random regular expressions:</p>
<pre><code>instance Arbitrary RE where
  arbitrary = genericArbitrary $ 1 % 5 % 5 % 2 % 3 % 1 % ()
  shrink = genericShrink
</code></pre>
<p>Notice that we're using the <code>Generic.Random</code> package and we generate regular expressions with probability 1/17 for <code>Null</code>, 5/17 for <code>Epsilon</code>, 5/17 for <code>Symbol</code>, etc. The use of this package also explains the <code>deriving Generic</code> in our definition of data type <code>RE</code>.</p>
<p>We will now test two properties: that the definition of <code>nullRE</code> is correct, i.e., for all regular expressions <code>r</code>, <code>nullRE r</code> is true iff <code>equivalent r Null</code>, and similarly for the definition of <code>epsRE</code>.</p>
<pre><code>prop_nullRE_correct :: RE -&gt; Bool
prop_nullRE_correct r = nullRE r == equivalent r Null

prop_epsRE_correct :: RE -&gt; Bool
prop_epsRE_correct r = epsRE r == equivalent r Epsilon

main = do
  let check = quickCheck . withMaxSuccess 10000
  check prop_nullRE_correct
  check prop_epsRE_correct
</code></pre>
<p>With the original definitions provided in the question, checking the first property succeeds after 10000 runs, but the second property almost immediately fails. QuickCheck generates a counterexample:</p>
<pre><code>$ stack runghc re-equiv.hs
+++ OK, passed 10000 tests.
*** Failed! Falsified (after 75 tests and 1 shrink):
Union Null Epsilon
</code></pre>
<p>We can easily verify that <code>Union Null Epsilon</code> should mathematically be equivalent to <code>Epsilon</code>. With the provided definition of <code>epsRE</code>, however, it is not. The correct definition for <code>epsRE (Union r1 r2)</code> should allow for only one of the two expressions to be equivalent to <code>Epsilon</code>, provided that the other one is equivalent to <code>Null</code>.</p>
<p>We can fix the definition as follows:</p>
<pre><code>epsRE :: RE -&gt; Bool
epsRE Null = False
epsRE Epsilon = True
epsRE (Symbol _) = False
epsRE (Union r1 r2) = epsRE r1 &amp;&amp; nullOrEpsRE r2 || nullOrEpsRE r1 &amp;&amp; epsRE r2
epsRE (Concat r1 r2) = epsRE r1 &amp;&amp; epsRE r2
epsRE (Star r) = nullOrEpsRE r

nullOrEpsRE :: RE -&gt; Bool
nullOrEpsRE r = nullRE r || epsRE r
</code></pre>
<p>Then, QuickCheck succeeds for both properties:</p>
<pre><code>$ stack runghc re-equiv.hs
+++ OK, passed 10000 tests.
+++ OK, passed 10000 tests.
</code></pre>

CC BY-SA 4.0
2024-05-03T17:20:19.487Z
2024-05-03T17:20:19.487Z
nickie
<p>I'm studying about the regular expression, but I'm a little confused about the concept of 'equivalence'. When I want to check &quot;[[r]] ≡ [[ε]]&quot;, it's false if r is NULL, true if epsilon, false if symbol, true only if both are epsilon for union and concatenate operations, and true if both are true for kleene star operations, and true only if NULL and epsilon?</p>
<hr />
<pre><code>nullRE :: RE -&gt; Bool
nullRE Null = True
nullRE Epsilon = False
nullRE (Symbol _) = False
nullRE (Union r1 r2) = nullRE r1 &amp;&amp; nullRE r2
nullRE (Concat r1 r2) = nullRE r1 || nullRE r2
nullRE (Star r) = False

epsRE :: RE -&gt; Bool
epsRE Null = False
epsRE Epsilon = True
epsRE (Symbol _) = False
epsRE (Union r1 r2) = epsRE r1 &amp;&amp; epsRE r2
epsRE (Concat r1 r2) = epsRE r1 &amp;&amp; epsRE r2
epsRE (Star r) = nullRE r || epsRE r
</code></pre>
<hr />
<p>Above is a Haskell code that expresses this. Is there anything wrong?</p>
<p>I tried Googling, but I couldn't get anything.</p>

CC BY-SA 4.0
2024-05-02T23:55:12.333Z
Your question is not particularly clear. If `nullRE r` and `epsRE r` stand for "is r equivalent to `Null` and `Epsilon`, respectively, then your definitions are correct. I assume that `Null` denotes a regular expression that generates the empty language.
nickie
CC BY-SA 4.0
2024-05-03T00:54:27.733Z
On second thought, no it isn't... `epsRE (Union r1 r2)` is wrong.
nickie
<regular-expressions>
Equivalence of regex in Programming language theory
Kleenex
# Equivalence of regex in Programming language theory

(Asked by: username_0 on 2024-05-01)

I'm studying about the regular expression, but I'm a little confused about the concept of 'equivalence'. When I want to check "[[r]] ≡ [[ε]]", it's false if r is NULL, true if epsilon, false if symbol, true only if both are epsilon for union and concatenate operations, and true if both are true for kleene star operations, and true only if NULL and epsilon?

nullRE :: RE -> Bool
nullRE Null = True
nullRE Epsilon = False
nullRE (Symbol _) = False
nullRE (Union r1 r2) = nullRE r1 && nullRE r2
nullRE (Concat r1 r2) = nullRE r1 || nullRE r2
nullRE (Star r) = False

epsRE :: RE -> Bool
epsRE Null = False
epsRE Epsilon = True
epsRE (Symbol _) = False
epsRE (Union r1 r2) = epsRE r1 && epsRE r2
epsRE (Concat r1 r2) = epsRE r1 && epsRE r2
epsRE (Star r) = nullRE r || epsRE r


Above is a Haskell code that expresses this. Is there anything wrong?
I tried Googling, but I couldn't get anything.

**Tags:** regular-expressions

> **Comments:**
> **username_1**: Your question is not particularly clear. If `nullRE r` and `epsRE r` stand for "is r equivalent to `Null` and `Epsilon`, respectively, then your definitions are correct. I assume that `Null` denotes a regular expression that generates the empty language.  
> **username_1**: On second thought, no it isn't... `epsRE (Union r1 r2)` is wrong.  

---

## 1 answers

### Answer by username_1 on 2024-05-03. Score: 1 | Accepted answer

I will give this a go, so that next time somebody is Googling it they can find it . I will try to make this educational and use Haskell, as the question suggests.

Let us first define a data type for regular expressions. Notice the difference between Epsilon (commonly noted as $\lambda$ or $\epsilon$), which matches the empty string, and Null (sometimes noted as $\emptyset$, but not found commonly in the definition of regular expressions), which does not match any string, i.e., it generates the empty language.
data RE = Null | Epsilon | Symbol Char | Union RE RE | Concat RE RE | Star RE
  deriving (Eq, Show, Generic)

Let us also define a function that produces the language generated by a regular expression. This function produces a (possibly infinite) list of strings, which does not necessarily contain unique elements.
gen :: RE -> [[Char]]
gen Null = []
gen Epsilon = [[]]
gen (Symbol c) = [[c]]
gen (Union r1 r2) = gen r1 ++ gen r2
gen (Concat r1 r2) | null l1 || null l2 = []
                   | otherwise = [s1 ++ s2 | s1 <- l1, s2 <- l2]
  where l1 = gen r1
        l2 = gen r2
gen (Star r) = l
  where l = [] : [s ++ s_star | s <- gen r, s /= [], s_star <- l]

The definition of gen is straightforward except for two points:

In concatenation, the second rule would suffice mathematically. However, if r1 generates an infinite language and r2 generates an empty language, the list comprehension would give an infinite loop. We solve this by bailing out immediately, in the case of empty languages.
In Kleene's star, we generate the empty string up front, then we exclude empty strings from the language generated by r. Without this, the list comprehension would be stuck producing an infinite list of empty strings.

Then, we define the equivalence of regular expressions. Mathematically, r1 is equivalent to r2 iff the language gen r1 is equal to the language gen r2. However, in Haskell, these languages are represented by infinite lists of strings and checking for their equality would be problematic because of three reasons:

strings in the list may occur multiple times,
the order of strings in the list is important, and
checking the equality of two equal infinite lists takes infinite time.

We will therefore make a simplification, which suffices for the purpose of what we're trying to show here. We define gen' by taking the list that consists of the first 100 strings generated by gen, sorting them and excluding duplicate elements. Then we define regular expression equivalence by comparing the results of gen'.
import Data.List

gen' :: RE -> [[Char]]
gen' = nub . sort . take 100 . gen

equivalent :: RE -> RE -> Bool
equivalent r1 r2 = gen' r1 == gen' r2

Notice that, strictly speaking, this definition of equivalence is mathematically wrong. As I said, however, it suffices for what we're trying to do here, as we are only interested in equivalence with Null and Epsilon, whose languages are finite and contain 0 and 1 elements, respectively.
Then, we will use QuickCheck for proving (or disproving) that the definitions for nullRE and epsRe are correct. QuickCheck is the seminal library for property-based testing. We will need the following lines in our preamble:
{-# LANGUAGE DeriveGeneric #-}
import Generic.Random
import GHC.Generics

import Test.QuickCheck

as well as the following, for generating random regular expressions:
instance Arbitrary RE where
  arbitrary = genericArbitrary $ 1 % 5 % 5 % 2 % 3 % 1 % ()
  shrink = genericShrink

Notice that we're using the Generic.Random package and we generate regular expressions with probability 1/17 for Null, 5/17 for Epsilon, 5/17 for Symbol, etc. The use of this package also explains the deriving Generic in our definition of data type RE.
We will now test two properties: that the definition of nullRE is correct, i.e., for all regular expressions r, nullRE r is true iff equivalent r Null, and similarly for the definition of epsRE.
prop_nullRE_correct :: RE -> Bool
prop_nullRE_correct r = nullRE r == equivalent r Null

prop_epsRE_correct :: RE -> Bool
prop_epsRE_correct r = epsRE r == equivalent r Epsilon

main = do
  let check = quickCheck . withMaxSuccess 10000
  check prop_nullRE_correct
  check prop_epsRE_correct

With the original definitions provided in the question, checking the first property succeeds after 10000 runs, but the second property almost immediately fails. QuickCheck generates a counterexample:
$ stack runghc re-equiv.hs
+++ OK, passed 10000 tests.
*** Failed! Falsified (after 75 tests and 1 shrink):
Union Null Epsilon

We can easily verify that Union Null Epsilon should mathematically be equivalent to Epsilon. With the provided definition of epsRE, however, it is not. The correct definition for epsRE (Union r1 r2) should allow for only one of the two expressions to be equivalent to Epsilon, provided that the other one is equivalent to Null.
We can fix the definition as follows:
epsRE :: RE -> Bool
epsRE Null = False
epsRE Epsilon = True
epsRE (Symbol _) = False
epsRE (Union r1 r2) = epsRE r1 && nullOrEpsRE r2 || nullOrEpsRE r1 && epsRE r2
epsRE (Concat r1 r2) = epsRE r1 && epsRE r2
epsRE (Star r) = nullOrEpsRE r

nullOrEpsRE :: RE -> Bool
nullOrEpsRE r = nullRE r || epsRE r

Then, QuickCheck succeeds for both properties:
$ stack runghc re-equiv.hs
+++ OK, passed 10000 tests.
+++ OK, passed 10000 tests.


---

