Allen Career Institute:TOC1

Question

The value of a regular expression r over ∑, denoted by Val(r), is defined as follows : 1. Val (Ø) = 0 2. Val (ε) = 0 3. Val (a) = 0 for every a ε ∑ 4. Val ((r. s)) = Val ((r + s)) = max(Val (r), Val (s)) 5. Val ((r*)) = Val (r) + 1

Find the value of regular expression (a (a + a*a a))

(1)

3

(2)

2

(3)

1

(4)

0

How max function working here? 

Answer 1

$Val(a(a+a^*aa))=max(val(a),val(a+a^*aa))$

$=max(0, val(a+a^*aa))$

$=max(val(a),val(a^* aa))$

$=max(0, val(a^*aa))$

$=max(0,max(val(a^*),val(aa)))$

$=max(val(a^*),0)\;\;$

($   \because val(aa)=max(val(a),val(a))=max(0,0)=0$

$=max((val(a)+1),0)$

$=1$