Question

Design an efficient algorithm to compute the number of binary strings with length n that satisfy 1 the regular expression ((0 + 11 + 101)∗ (1101))∗ .

Answer 1

ANSWER :

GIVEN THAT :

We can solve this question with the help of constructing a finite state machine and then designing a dynamic programming approach to solve the same.

Look at the below Finite state machine representing the regular expresion ( (0+10+101)(1101)).

Here, S,S1,F are three states where S is the start state and F is the final state.
Points to notice,We can create one 0 length string but we cannot create strings of length 1, 2 and 3. as (1101) is present.
From S, on having a string of length 1(0) or length 2(11) or length 3(101) we go to S1. In S1, we add (1101) to it and move to final state(if that is the termination of string) or move to S again to repeat the string (to perform the kleene star {*} operation).

Now, we will design a dynammic programming approach. We know number of string of length 0 that can be formed is 1 and number of strings of length 1,2 and 3 are 0. So,we will find out the number of strings of length l that can be formed in all the three states. i.e S,S1 and F. In the end, we will be intersted in the answer produced by F as it is the final state.

Consider,three arrays of length N+1:
DP_S[L] which gives the number of strings that can be formed in state S having length L.
Similarly, DP_S1[L] which gives the number of strings that can be formed in state S having length L.
and DP_F[L] which gives the number of strings that can be formed in state S having length L.

Algorithm:

1. Initialize DP_S[0] = 1 , DP_S1[0] = 1 and DP_F[0] = 1 (as number of strings of length 0 that can be formed is 1)

2. If L-4 > 0
DP_S[L] = DP_S1[L]
else
DP_S[L] = 0 (as number of strings of length 1,2,3 are 0)

3. DP_S1[L] = DP_S[L] + DP_S[L-1] + DP_S[L-2] + DP_S[L-3]
(number of strings in S1 of length L is sum of the number of strings of length L,L-1,L-2 and L-3 in state S as from state S, on generating a string of length 0 (null) or 1 (string 0) or 2 (string 11) or 3 (string 101) we move to state S1)

4. DP_F[L] = DP_S1[L-4] + DP_S[L]
(Similarly, from state S we can go to state F on null (same length string) or S1 we can go to F upon string 1101 (string of length 4). Hence, number of strings in F of length L is sum of the number of strings of length L in state S and number of strings of length L-4 in state S1)

5. DP_F[N] will return the total number of strings of length N that can be formed .