Computer science: Theory Of computation MCQs

Let L = {w ∈ (0 + 1)*|w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expressions below represents L?

Consider the languages  L1 = {0i1j| i != j} . L2 = {0i1j| i = j} . L3 = {0i1j| i = 2j + 1} . L4 ={0i1j| i != 2j }. Which one of the following statements is true?

Let w be any string of length n in {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?

The lexical analysis for a modern computer language such as Java needs the power of which one of the following machine models in a necessary and sufficient sense?

Let P be a regular language and Q be a context free language such that Q⊆P. (For example, let P be the language represented by the regular expression p*q* and Q be {pnqn|n∈N}. Then which of the following is ALWAYS regular?