Hi, I am totally stuck on these set of questions. Any help would beappreciated.

Question

Hi,

I am totally stuck on these set of questions. Any help would beappreciated.

Use axymptotic (big-O) notation to answer the followingquestions.

a) Let N be an NFA that has n states. If we convert N to anequivalent DFA M, how many states would M have?

b) Let R be a regular expression that has n symbols (eachconstant/operation counts as one symbol). If we convert R to anequivalent NFA N, how many states would N have in the worstcase?

c) Let M be a DFA that has n states. If we convert M to anequivalent regular expression R, how many symbols would R have inthe worst case?

Explanation / Answer

Dear User, a) The DFA M accepts (means it is in an accept state) if oneof the possible states that the NFA N could be in at this point, isan accept state.Every NFA has an equivalent DFA. If k is the number of states of the NFA, it has2k subsets of states. Each subset corresponds to one ofthe possibilities that the DFA must remember,So, the DFA simulatingthe NFA. Therefore, DFA ‘M’ have ‘2kstates’ b) Every regular expression has an equivalent NFA (they matchthe same strings) and vice versa. For every regular expression Rthere exists an NFA N such that L(R) = L(N). So, the number of states in the final NFA is at most equal tothe length of the original regular expression. ITS HELPFUL TO YOU.... So, the number of states in the final NFA is at most equal tothe length of the original regular expression. ITS HELPFUL TO YOU....

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.