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

The Gateway to Computer Science Excellence

+1 vote

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,306 answers

198,321 comments

105,014 users