Chapter 3b

Benjie Pabroa

Example  Consider the language T defined over the

alphabet Σ = {a b c}: T = {a c ab cb abb cbb abbb cbbb abbbb cbbbb . . .} All the words in T begin with an a or c and then followed by some number of b’s. Symbolically, we may write this as T = language(a+c)b*) = language(either a or c then some b’s)

Example Now let us consider a finite language L that

contains all the strings of a’s and b’s of length three exactly: L ={aaa aab aba abb baa bab bba bbb} Observe, examine and try to construct the Regular Expression of the given language Consider the expression (a+b)5= (a+b) (a+b) (a+b) (a+b) (a+b) -define a language that begin with letter a, and a language that begin with a and end

DEFINITION

The symbols that appear in regular expressions are the letters of the alphabet Σ, the symbol for the null string Λ, parenthesis, the star operator, and the plus sign. The set of regular expressions is defined by the following rules: RULE 1: Every letter of Σ can be made into a regular expression by writing it in boldface; Λ itself is a regular expression.

DEFINITION continued…

RULE 2 If r1 and r2 are regular expressions, then so are: (i) (r1) (ii)

r1 r2

(iii)

r1 + r2

(iv)

r1*

RULE 3 

Nothing else is a regular expression.

Let us emphasize the implicit parentheses in

r1*. If r1= aa + b, then the expression r1* technically refers to the expression r1* = aa + b*

which is the formal concatenation of the symbols r1 with the symbol *, but what we generally mean when we write r1* is actually (r1)*: r1*=(r1)*=(aa + b)* which is different.

EXAMPLE

Let us consider the language defined by the expression (a + b)*a(a + b)* For example, the word abbaab can be derived from this expression by three different ways. (Try to derive)

 If the only words left out of the language defined

by the expression above are the words without a’s (Λ and strings of b’s), then these omitted words are exactly the language defined by the expression b*. If we combine these two, we should produce the language of all strings. In other words, since all strings = (all strings with an a) + (all strings without an a)

it should make sense to write (a + b)* = (a + b)*a(a + b)*+ b*

Notice that this use of the plus sign is far from

the normal meaning of addition in the algebraic sense, as we can see from a*=a*+a* a*=a*+a*+a* a*=a*+aaa In algebra, they lead to presumptions of subtractions that are misguided

EXAMPLE

The language of all words that have at least two a’s can be described by the expression (a + b)*a(a + b)*a(a + b)* = (some beginning)(the first important a) (some middle)(the second important a) (some end) where the arbitrary parts can have as many a’s (or b’s) as they want. 

Examples:  Expression that denotes all the words with at

least two a’s  is (a+b)*a(a+b)*a(a+b)* is equal to b*ab*a(a+b)*  Write the expression that describe all words with exactly two a’s

 Write the expression that describe all words

that have at least one a and at least one b.

Construct expression defining each of the

following language over the alphabet Z={a,b}  All words in which a appears tripled, if at

all. This means that every clump of a’s contains 3 or 6 or 9 or 12….. a’s.  All words that contain exactly two b’s or exactly three b’s, not more.  All strings that end in a d ouble letter  All strings that do not end in a double letter