The question is unclear, could you please frame it properly ?

0 votes

2 votes

Best answer

There is a cool trick which i got to know from CLRS (Ex 22.4-2).

Since, this is a regular language , $\exists$ a dfa for it , we can have a graphical representation for it.

Check if the graph has a cycle , if yes then halt.

Otherwise,

Add an additional parameter , called weights to each vertex. Assign weights 1 to any of the final vertices first and assign it weight 1.

Create a topological ordering of it and traverse it from the reverse , i.e destination to source, for a node v , weights[v]=$\Sigma$ weights[v]+weights[w], where w are the adjacent vertices of v. Finally when it completes , check the weights of the initial state vertex. If it is $\geq$ 100, then stop , otherwise repeat for all final states and check whether it exceeds 100 or not. You will finally have your answer.

Since, this is a regular language , $\exists$ a dfa for it , we can have a graphical representation for it.

Check if the graph has a cycle , if yes then halt.

Otherwise,

Add an additional parameter , called weights to each vertex. Assign weights 1 to any of the final vertices first and assign it weight 1.

Create a topological ordering of it and traverse it from the reverse , i.e destination to source, for a node v , weights[v]=$\Sigma$ weights[v]+weights[w], where w are the adjacent vertices of v. Finally when it completes , check the weights of the initial state vertex. If it is $\geq$ 100, then stop , otherwise repeat for all final states and check whether it exceeds 100 or not. You will finally have your answer.