Basic rules

1. a

Set with only a single letter string { a }.

2. ε

Set with only a empty string { "" }

3. s|t

An element of sets s or t.

(alternation)

e.g.:

s  = { a }
t  = { c }

s|t = { a,c }

4. st

An element of set s is cotenated with a string an element from t.

(concatenation)

e.g.:

s  = { a,b }
t  = { c,d }

st = { ac,ad,bc,bd }

5. s*

Concatenation of any number of elements from subsets of s.

e.g.:

s  = { a,b }

s* = {  ε,a,b,aa,ab,ba,bb,aaa, ... }

Properties

Precedence

1. *
2. concatenation
3. |

e.g.:

a|ab* = a|(a(b*))

Algebraic properties

• (r|s|)t = r|s|t = r|(s|t)
• s|t = t|s
• s|s = s
• s ε = s =  ε s
• (rs)|t = rst = r(st)
• r ( s | t ) = rs | rt
• ( r | s ) t = rt | st
• (s*)* = s*
• s*s* = s*

Shorthands

• s? = s|ε
• s+ = ss* = s*s
• [st] = s|t