-1
$\begingroup$

Are the following two sets equal? One the set of regular expression over an alphabet, and the other set is the set of all strings which can be generated by using the symbols of an alphabet(Σ*)?

$\endgroup$
  • $\begingroup$ I don't understand what the question is here. Well, there is an answer, but it's so self-evident that I do not know why you have to ask. What's the real confusion? $\endgroup$ – Raphael Jan 13 '16 at 7:44
  • 3
    $\begingroup$ I suggest you check the definition of what a regular expression is and what strings in $\Sigma^*$ are. $\endgroup$ – David Richerby Jan 13 '16 at 7:44
  • $\begingroup$ Think about a simple alphabet with one symbol. Then write down Σ*. Can you find a regular expression that is not in Σ*? $\endgroup$ – user4758246 Jan 13 '16 at 7:44
4
$\begingroup$

Are [...] the set of regular expression[s] over [$\Sigma$] [...] and the set of all strings [in $\Sigma^*$] equal?

Since the types of objects don't even match, clearly not!

Going back to the definitions, regular expressions have a certain syntax. They contain symbols from the fixed alphabet $\Sigma$, but also operators not in $\Sigma$ like $+$, $\mid$, $^*$, and others. Their interpretations are formal languages over $\Sigma$. That is, if $R$ is a regular expression over $\Sigma$ then $L(R) \subseteq \Sigma^*$.

$\endgroup$
1
$\begingroup$

Regular Expression:

  1. a, for some a in the alphabet Σ.
  2. λ.
  3. Empty set.
  4. r + s
  5. r | s
  6. r*.

What is Σ* ?

Given an alphabet Σ, we can apply the Kleene Star operator * on it to get the set Σ* (read Σ-star), called the Kleene closure of Σ. The set Σ* is the set of all possible strings of all possible lengths on Σ including λ, the empty string, and is therefore infinite (if Σ is nonempty). Source

( 5 + 3 ) x 4 is an arithmetic expression, whose value is 32. Similarly, a regular expression is something, whose value is a language, i.e. which describes a language (set of strings).

So, all possible regular expressions, over an alphabet Σ describe Σ*.

References: Intro to Theory of Computation by Sipser. Chapter Automata & Languages -> Regular Expressions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.