Q. The length of the shortest string NOT in the language (over Σ = {a, b}) of the following regular expression is ______________.

a*b*(ba)*a*

View solution

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

View solution

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?

View solution

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

View solution

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

View solution

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

View solution

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?

View solution

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?

View solution

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

View solution

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

View solution

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.

View solution

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?

View solution

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

View solution

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)?

View solution

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

View solution

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?

View solution

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

View solution

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

View solution

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?

View solution

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?

View solution