retagged by
562 views
0 votes
0 votes

Given regular expression : a*(b+c)*abc* 

f(n) denote number of string of length N generated by given regular expression. which of the following best describes the growth of f(N) as N increses 

1. Linear

2.quadratic

3.Cubic

4.Logarithmic

5.Exponential

retagged by

1 Answer

Best answer
3 votes
3 votes

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

Related questions

0 votes
0 votes
1 answer
1
iam.sahilpatra asked Sep 16, 2023
201 views
Solve this using Adrens lemma rule.
0 votes
0 votes
1 answer
2
3 votes
3 votes
0 answers
3
Nikhil Patil asked Aug 15, 2017
459 views
What is Time Complexity of 4T ( n /2 ) + n / logn ?
1 votes
1 votes
0 answers
4
Ankush Tiwari asked Jul 27, 2016
648 views
T(n)=sqrt(2T(n/2))+logn