Log In
0 votes
Given an algorithm to tell whether a regular language
L contains at least 100 strings
in Theory of Computation 111 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

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.


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.

selected by
Can you please explain this in some simpler way?
or any reference link?

Refer to Exercise 22.4-2 here

Related questions

1 vote
1 answer
If a DFA "D" have symbol {0,1,2} and NFA "N" have symbol {0,1} but both are representing strings ending with 01 and whole string only contain {0,1} then can we say L(N) = L(D) i.e language represented by DFA is equal to language represented by NFA?
asked Feb 20, 2019 in Theory of Computation Bhaskar Singh 196 views
0 votes
1 answer
Construct a minimal DFA which accepts set of all strings over {a,b}, such that $1)$Second symbol from $RHS$ should be $‘a’$ $2)$Third symbol from $RHS$ should be $‘a’$
asked Dec 27, 2018 in Theory of Computation Lakshman Patel RJIT 147 views
0 votes
2 answers
DFA in which 01 and 10 have equal number of occurrences
asked Dec 14, 2018 in Theory of Computation aditi19 376 views
1 vote
1 answer
in reversal of DFA if there are more than one final states then which one will be made the initial state? a DFA can have only one initial state
asked Dec 10, 2018 in Theory of Computation aditi19 657 views