I think it should be exponential
First we will draw nfa for given regular expression
now minimum length of string that can be obtained is 2 which is 'ab'.
case i) number of strings possible with length 2
length |
strings |
Number of strings possible |
2 |
ab |
1 |
|
|
So total possible = 1 |
case ii) number of strings possible with length 3
length |
strings |
Number of strings possible |
Reason |
3 |
ab_ |
1 |
the blank can only be replace by c that's why only 1 |
|
_ab |
3 |
the blank can only be replace by a, b or c that's why 3 |
|
|
So total possible =1+3=4 |
|
case iii) number of strings possible with length 4
length |
strings |
Number of strings possible |
Reason |
4 |
ab_ _ |
1 |
the blank can only be replace by c that's why only 1 |
|
_abc |
3 |
the blank can only be replace by a, b or c that's why 3 |
|
_ _ ab |
9 |
first blank can be filled in 3 ways and similarly the second one |
|
|
So total possible = 1+3+9 = 13 |
|
case iv) number of strings possible with length 5
length |
strings |
Number of strings possible |
Reason |
5 |
ab_ _ _ |
1 |
the blank can only be replace by c that's why only 1 |
|
_abcc |
3 |
the blank can only be replace by a, b or c that's why 3 |
|
_ _ abc |
9 |
first blank can be filled in 3 ways and similarly the second one |
|
_ _ _ ab |
27 |
first blank can be filled in 3 ways and similarly the second and third one |
|
|
So total possible = 1+3+9+27=40 |
|
From above tables we observe that number of possible string with length N is given by,
length = 1+3+9+......+3N-1
= $\frac{3^{N}-1}{3-1}$
= $\frac{3^{N}-1}{2}$
= O(3N)
hence exponential
Plz check if I am correct @Arjun sir