Q. Given the language L = {ab, aa, baa}, which of the following strings are in L*?

1) abaabaaabaa
2) aaaabaaaa
3) baaaaabaaaab
4) baaaaabaa

View solution

Q. Let w be any string of length n is {0,1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?

View solution

Q. Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?

View solution

Q. Which one of the following is FALSE?

View solution

Q. Which of the following statements is false?

View solution

Q. Which of the following is TRUE?

View solution

Q. A minimum state deterministic finite automaton accepting the language L={w | w ε {0,1} *, number of 0s and 1s in w are divisible by 3 and 5, respectively} has

View solution

Q. Let L1 = {w ∈ {0,1}∗ | w has at least as many occurrences
of (110)’s as (011)’s}.

Let L2 = { ∈ {0,1}∗ | w has at least as many occurrences
of (000)’s as (111)’s}.

Which one of the following is TRUE?

View solution

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