The computation of e-closure of n-states takes ______ time.(a) O(n^2)(b) O(n^3)(c) O(2^n)(d) None of the mentionedThis question was posed to me in an interview.My question comes from Conversions among Representations topic in chapter Properties of Regular Languages of Automata Theory

The computation of e-closure of n-states takes ______ time.(a) O(n^2)(

1.	The computation of e-closure of n-states takes ______ time.(a) O(n^2)(b) O(n^3)(c) O(2^n)(d) None of the mentionedThis question was posed to me in an interview.My question comes from Conversions among Representations topic in chapter Properties of Regular Languages of Automata Theory
Answer» RIGHT answer is (b) O(n^3) Best explanation: We MUST SEARCH from each of the n states along all arcs LABELLED e. If there are n states, there can be no more than n^2 states.

Discussion

No Comment Found

Related InterviewSolutions

State true or false:Statement: Regular expression can directly be converted to DFA without intermediate steps.(a) Statement: Regular expression can directly be converted to DFA without intermediate steps.(b) true(c) falseThis question was addressed to me in a national level competition.The doubt is from Conversions among Representations in portion Properties of Regular Languages of Automata Theory
Which of the following is a function of Closure properties?(a) Helps construct representations(b) Helps show informally described languages not to be in class(c) Both (a) and (b)(d) None of the mentionedI have been asked this question in examination.The question is from Testing Emptiness and Membership topic in portion Properties of Regular Languages of Automata Theory
Which of the following are not meant to specify a regular language?(a) Regular Expression(b) DFA(c) NDFA and epsilon-NFA(d) All of the mentionedThe question was asked in class test.I need to ask this question from Testing Emptiness and Membership in division Properties of Regular Languages of Automata Theory
Which of the following are decision properties?(a) Emptiness(b) Infiniteness(c) Membership(d) All of the mentionedThe question was posed to me in my homework.My doubt is from Testing Emptiness and Membership in division Properties of Regular Languages of Automata Theory
Language classes have the following property:(a) Closure property(b) Decision property(c) Closure & Decision property(d) None of the mentionedI got this question in an international level competition.Asked question is from Testing Emptiness and Membership in division Properties of Regular Languages of Automata Theory
Which of the following problems do not belong to decision properties?(a) Given two languages, are there strings that are in both(b) Is the language a subset of another regular language(c) Is the language same as another regular language(d) None of the mentionedI had been asked this question by my college director while I was bunking the class.Query is from Testing Emptiness and Membership topic in section Properties of Regular Languages of Automata Theory
Pick the odd one out of the given properties of a regular language:(a) Kleene(b) Reversal(c) Homomorphism(d) MembershipI had been asked this question in class test.My enquiry is from Testing Emptiness and Membership topic in division Properties of Regular Languages of Automata Theory
If L1′ and L2′ are regular languages, then L1.L2 will be(a) regular(b) non regular(c) may be regular(d) none of the mentionedThe question was asked during an interview.I would like to ask this question from Closure Properties under Boolean Operations topic in portion Properties of Regular Languages of Automata Theory
The language of balanced paranthesis is(a) regular(b) non regular(c) may be regular(d) none of the mentionedThe question was posed to me in examination.The above asked question is from Applications of Pumping Lemma/Pigeonhole principle topic in portion Properties of Regular Languages of Automata Theory
Let w= xyz and y refers to the middle portion and |y|>0.What do we call the process of repeating y 0 or more times before checking that they still belong to the language L or not?(a) Generating(b) Pumping(c) Producing(d) None of the mentionedI had been asked this question in a job interview.This interesting question is from Pumping Lemma for Regular Language in division Properties of Regular Languages of Automata Theory

The computation of e-closure of n-states takes ______ time.(a) O(n^2)(b) O(n^3)(c) O(2^n)(d) None of the mentionedThis question was posed to me in an interview.My question comes from Conversions among Representations topic in chapter Properties of Regular Languages of Automata Theory

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment