56 views
Given an algorithm to tell whether a regular language
L contains at least 100 strings
| 56 views
0
The question is unclear, could you please frame it properly ?
0
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.
0

@Arkaprava

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

+1 vote
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.
by Active (2.4k points)
selected
0
Can you please explain this in some simpler way?
0

Refer to Exercise 22.4-2 here http://sites.math.rutgers.edu/~ajl213/CLRS/Ch22.pdf

+1 vote