Viewing topic: 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.