CMPSC 138 Chapter Notes - Chapter 3: Regular Grammar, Regular Language, Regular Expression
Document Summary
, , and are all regular expressions, called primitive regular expressions. If " and ( are regular expressions, so are " + (, " (, ". A string is a regular expression if and only if it can be derived from the primitive regular expressions by a finite number of applications of the rules in (2) The language () denoted by any regular expression is defined by the following rules: Is a regular expression denoting the empty set is a regular expression denoting {} For every , is a regular expression denoting {} If " and ( are regular expressions, then: Precedence rules for evaluation: star-closure precedes concatenation precedes union. 3. 2 connection between regular expressions and regular languages. The converse of the above theorem also holds: For every regular language, there should exist a corresponding regular expression. Generalized transition graph (gtg) = a transition graph whose edges are labelled with regular expressions.
