3.1 REGULAR EXPRESSIONS
One way of describing regular languages is via the notation of regular expressions. This notation involves a combination of strings of symbols from some alphabet Σ, parentheses, and the operators +, ·, and *. The simplest case is the language {a}, which will be denoted by the regular expression a. Slightly more complicated is the language {a, b, c}, for which, using the + to denote union, we have the regular expression a + b + c. We use · for concatenation and * for star-closure in a similar way. The expression (a + (b · c))* stands for the star-closure of {a}∪{bc}, that is, the language {λ, a, bc, aa, abc, bca, bcbc, aaa, aabc, …}.
Formal Definition of a Regular Expression
We construct regular expressions from primitive ...
Get An Introduction to Formal Languages and Automata, 7th Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
