Regular Expressions and their Languages

Definition 1.26:

$\QTR{Large}{R}$ is a regular expression over the alphabet MATHif:

  1. $\QTR{Large}{R}$ $\QTR{Large}{=a}$, with MATH

  2. MATH

  3. MATH

  4. MATH, with $\QTR{Large}{R}_{1}$ and $\QTR{Large}{R}_{2}$ regular expressions.

  5. MATH with $\QTR{Large}{R}_{1}$ and $\QTR{Large}{R}_{2}$ regular expressions.

  6. MATH, with $\QTR{Large}{R}_{1}$ a regular expressions.

---------------------------------------------------------

note: The use of brackets in the above definition avoids issues of operator precedence. In general, star MATH is considered to be of higher precedence than concatenation (0 ) , which in turn is higher than union MATH. Thus MATH reads, "apply star to the union of $\QTR{Large}{R}_{1}$ and $\QTR{Large}{R}_{2}$ . And

MATH reads take the union of $\QTR{Large}{R}_{1}$ and MATH .

---------------------------------------------------------

Definitions :

Given a regular expression $\QTR{Large}{R}$ over the alphabet MATH, we define $\QTR{Large}{L(R)}$ , the language of $\QTR{Large}{R}$, recursively as a set of strings in MATHas follows:

  1. if $\QTR{Large}{R}$ $\QTR{Large}{=a}$, with MATH, then MATH, the set with the single string "$\QTR{Large}{a}$".

  2. if MATH, then MATH, the set with the single string being the empty string.

  3. MATH, then MATH, the empty set of strings.

  4. MATH, with $\QTR{Large}{R}_{1}$ and $\QTR{Large}{R}_{2}$ regular expressions, then MATH, the union of the two sets of strings.

  5. MATH with $\QTR{Large}{R}_{1}$ and $\QTR{Large}{R}_{2}$ regular expressions, then MATH MATH MATH

  6. MATH, with $\QTR{Large}{R}_{1}$ a regular expressions,

    then MATH MATH.

Finally we say MATH if and only if MATH

---------------------------------------------------------

Examples:

  1. MATH

  2. MATH

  3. MATH

  4. MATH only if MATH, else MATH

________________________________________________________

Assignment 2 ,due Sept. 15

Sipser Pages 84-85 :

1.5 a,b,c

1.6 a.

1.10

________________________________________________________

Generalized Nondeterministic Finite Automata Notes

________________________________________________

________________________________________________