The Gateway to Computer Science Excellence
0 votes
Given an algorithm to tell whether a regular language
L contains at least 100 strings
in Theory of Computation by Active (2.3k points) | 56 views
The question is unclear, could you please frame it properly ?
We can make a Finite Automata and can check whether we are getting atleast 100 different ways to reach from initial state to final state.

finding the ways would depend on the constraints given for that language.


Need to  know a method by which we can say that the DFA produces >=100 strings

1 Answer

+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.


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.
by Active (2.4k points)
selected by
Can you please explain this in some simpler way?
or any reference link?

Refer to Exercise 22.4-2 here

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,306 answers
105,014 users