1) Give Reason ( Algorithms for Finite Automata and whether polynomial or expone
ID: 3701646 • Letter: 1
Question
1) Give Reason ( Algorithms for Finite Automata and whether polynomial or exponential, if not given in question, and why ? )
a) There is an exponential algorithm which, given a nondeterministic finite automaton, constructs an equivalent deterministic finite automaton. ? WHY ?
b) There is an exponential algorithm which, given a nondeterministic finite automaton, constructs an equivalent regular expression. WHY ?
(d) There is a polynomial algorithm which, given a deterministic finite automaton, constructs an equivalent deterministic finite automaton with the smallest possible number of states. WHY
Explanation / Answer
a) This is because for every pair of integers n,a ,there exists a minimum non deterministic finite automation for n<=a <=2^n with n states where the corresponding equivalent DFA has a states. If we avoid non determinisim in Non deterministic finite automate then DFA will have exponential number of states.
b) We first need to convert the DFA into NFA. Reduce the number of states of NFA to two states using the ripping states process. Now the reduced NFA states is converted to its corresponding Regex using the following process:
NFA has only 2 states.The initial state and the accepting state.Since there are no self loops for the inital and accepting states we assume that NFA N with 2 states accepts all words that is matching the regular expressions.
Those strings that matches the regex causes the NFA to end in a double circle state.Those Strings that causes the NFA to end in the accept state will also match the regex.
d) Reducing the size of a NFA is to reduce the search time. Polynomial algorithms are used for NFA minimization because they are helpful in minimizing the running time
A NFA minimization is PSPACE complete(PSPACE is something that can be solved using the amount of memory or storage) or any problem involving PSPACE can be resolved by applying the Polynomial algorithm.
The main idea behind using Polynomial Algorithm is that the reduction of steps can be done faster in polynomial time.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.