adplus-dvertising
frame-decoration

Question

Consider the regular language L = (111 + 11111)*. The minimum number of states in any DFA accepting this languages is:

a.

3

b.

5

c.

8

d.

9

Answer: (d).9

Engage with the Community - Add Your Comment

Confused About the Answer? Ask for Details Here.

Know the Explanation? Add it Here.

Q. Consider the regular language L = (111 + 11111)*. The minimum number of states in any DFA accepting this languages is:

Similar Questions

Discover Related MCQs

Q. Let Nf and Np denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let Df and Dp denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata, respectively. Which one of the following is TRUE?

Q. The regular expression 0*(10*)* denotes the same set as

Q. The smallest finite automation which accepts the language {x | length of x is divisible by 3} has :

Q. Given an arbitary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least

Q. Consider a DFA over ∑ = {a, b} accepting all strings which have number of a’s divisible by 6 and number of b’s divisible by 8. What is the minimum number of states that the DFA will have?

Q. Let S and T be language over Σ = {a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true?

Q. Let L denotes the language generated by the grammar S -> 0S0/00. Which of the following is true?

Q. What can be said about a regular language L over {a} whose minimal finite state automaton has two states?

Q. How many minimum states are required in a DFA to find whether a given binary string has odd number of 0's or not, there can be any number of 1's.

Q. Consider alphabet ∑ = {0, 1}, the null/empty string λ and the sets of strings X0, X1 and X2 generated by the corresponding non-terminals of a regular grammar. X0, X1 and X2 are related as follows:

X0 = 1 X1
X1 = 0 X1 + 1 X2
X2 = 0 X1 + {λ}

Which one of the following choices precisely represents the strings in X0?

Q. The number of states in the minimal deterministic finite automaton corresponding to the regular expression (0 + 1)*(10) is ____________

Q. Let T be the language represented by the regular expression Σ∗0011Σ∗ where Σ = {0, 1}. What is the minimum number of states in a DFA that recognizes L' (complement of L)?

Q. Which one of the following regular expressions is NOT equivalent to the regular expression (a + b + c) *?

Q. Let L be a regular language and M be a context-free language, both over the alphabet Σ. Let Lc and Mc denote the complements of L and M respectively. Which of the following statements about the language Lc∪ Mc is TRUE?

Q. Which of the following statements is TRUE about the regular expression 01*0?

Q. The language {0^n 1^n 2^n | 1 ≤ n ≤ 10^6} is

Q. A language L satisfies the Pumping Lemma for regular languages, and also the Pumping Lemma for context-free languages. Which of the following statements about L is TRUE?

Q. Consider the context-free grammar E → E + E E → (E * E) E → id
where E is the starting symbol, the set of terminals is {id, (,+,),*}, and the set of nonterminals is {E}.
Which of the following terminal strings has more than one parse tree when parsed according to the above grammar?

Q. Consider the context-free grammar E → E + E E → (E * E) E → id
where E is the starting symbol, the set of terminals is {id, (,+,),*}, and the set of non-terminals is {E}.
For the terminal string id + id + id + id, how many parse trees are possible?

Q. The number of states in the minimum sized DFA that accepts the language defined by the regular expression (0+1)*(0+1)(0+1)* is __________________ .