Languages and Regular expressions - University of Illinois Urbana-Champaign

Languages and Regular expressions

Lecture 2

1

Strings, Sets of Strings, Sets of Sets of Strings...

? We defined strings in the last lecture, and showed some properties.

? What about sets of strings?

2

CS 374

n, *, and +

? n is the set of all strings over of length exactly n. Defined inductively as: ? 0 = {} ? n = n-1 if n > 0

? * is the set of all finite length strings: * = n0 n

? + is the set of all nonempty finite length strings: + = n1 n

3

CS 374

n, *, and +

? |n| = ?||n ? |?n| = ?

? ?0 = {} ? ?n = ??n-1 = ? if n > 0 ? |?n| = 1 if n = 0 |?n| = 0 if n > 0

4

CS 374

n, *, and +

? |*| = ?

? Infinity. More precisely, 0

? |*| = |+| = |N| = 0 ? How long is the longest string in *?

no longest string!

? How many infinitely long strings in *? none

CS 374

5

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download