Chapter 5: Nondeterministic Finite Automata

Do some exercises. Page 54. #2 pg 55 #4,5. Page 57 10

Chapter 6

The subset construction page 65

Convert NFA to DFA. theorem says NFA same as DFA

A language L is L(N) for some NFA N off L is a regular language.

Chapter 6: NFA Applications

Page 71, #3 Page 72 #5

## Chapter 7. Regular Expressions

Formal Definitions

Concatenation of languages

Kleene closure

{a,b}*

A regular expression is a string r that denotes a language L(r) over some alphabet S. The six kinds of regular expressions and languages…..

Page 76 .. 77

Examples pg 77-78

Regular Expression. —> Regular Language —-> Regular Expression

From another source:

Let Σ be a fixed alphabet.

A regular expression, or regexp for short, is an expression that describes a particular language over Σ.

If r is a regular expression, we write L(r ) for the language described by r .

We may also just use the regexp itself in place of the language it describes.

Primitive (atomic) regular expresions are:

- Φ describes the empty language L(Φ) = Φ;
- ε describes the language L(ε) = {ε } consisting of just the empty string; and
- a for a ε Σ describes the language L(a) = {a} consisting of just the string a of length 1.

Regular expressions can be combined with three possible operators: union, concatenation, and Kleene closure. If r and s are regexps, then so are:

- r+ s describing the language L(r ) U L(s);
- (rs), describing the language L(r )L(s);
- (r*) , describing the language L(r )*

Every regular expression is constructed by these rules; no other regular expressions are possible.

This is an inductive (recursive) definition, since it defined new regular expressions in terms of shorter ones (subexpressions).

Conventions

Parentheses are only used for grouping and can be dropped if we assume the following syntactic precedences: (r ) before r* before r+s

Both binary operations are associative, so we don’t care how they associate.

We will use r+ as shorthand for rr*, i.e., denoting concatenation of 1 or more strings from r .

Q: What is r+ + ε ?

Similarly, we will use rk = r r r r … r

Examples of Regular Expressions

Let Σ= {0,1}

0*10*={w | w contains a single 1}

Σ*1Σ* = { w| w contains at least one 1}

(ΣΣ)* = {w | the length of w is even }

What is (01+)?

What is 0Σ*0 U 1Σ*1 U 0 U 1

Chapter 7: Regular Expressions

Exercises page 85 exercise1, page 89 exercise 8

Chapter 8: Regular Expression Applications

Use egrep to find all numbers divisible by 4 in the file http://paprika.umw.edu/~ernie/cpsc326/numbers

or /users/ernie/public_html/cpsc326/numbers

got to /users/ernie/public_html.cpsc230

Which lines in /users/ernie/public_html/sum.cpp have in-line comments?

Which lines are comments?

Use Java to do the same