Viewing topic: Regular Expression

See sub-topics for Regular Expression ... >> Computer Science >> Theory >> Regular Expression

Highest Rated Sign

Video id: #2934 (enlarge)
Post date: 1/4/2013
Posted by: D_Seita
Rating:
  • Currently 0.0/5 Stars.
  0 ratings
See all signs (1)

Regular Expression

  • Definition: A regular expression in a finite alphabet A is defined recursively. Base case: A symbol in A or L (lambda). Recursive case: if x and y are regular expressions then so are (xy), (xUy), and x*. Each regular expression defines a set of strings. A member a of A defines the set {a} and the symbol L defines {}, the empty set. The set defined by (xy) is the set of strings formed by concatenating a string from the set defined by x with a string from the set defined by y. The set defined by (xUy) is the union of the set defined by x and the set defined by y. Finally, the set defined by x* is the set of strings formed by concatenating any number of strings from the set defined by x together. One special case is concatenating zero strings from the set defined by x together. This means L is in the set defined by x* for any x. The parentheses are often dropped using the normal precedence of concatenation and union.

  • Example: (00 U 11)* defines the set {L, 00, 11, 0000, 0011, 1100, 1111, ...}

  • There are no comments for this topic.