In my book:

  • The set {abb, a, b, bba} is said to be converted into regular expression abb + a + b + bba.
  • The set {01, 10} to regular expression 01 + 10

Does the +'s here represent concatenation or union?

  • 3
    $\begingroup$ In regular expressions, $+$ is union $\endgroup$ – vonbrand Nov 12 '15 at 9:37
  • 1
    $\begingroup$ There is only one true answer: looks at the definition. $\endgroup$ – Raphael Nov 12 '15 at 10:59

We don't quite convert a set to a regular expression. Rather, we give a regular expression for a language (i.e., a regular expression which defines the same language). For example, a regular expression for the language $\{01,10\}$ is $01+10$, and a regular expression for the language $\{abb,a,b,bba\}$ is $a+b+abb+bba$. There can be other regular expressions. For example, another regular expression for the second language is $a(\epsilon+bb) + b(\epsilon+ba)$.

Regarding the syntax of regular expressions, this should be explained in your book.


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.