Test: Finite Automata: Regular Languages- 1 - Computer Science Engineering (CSE) MCQ

There are some NFA's for which no DFA can be constructed.
Explanation:

Option 3 is false because every NFA (Nondeterministic Finite Automaton) can be converted into an equivalent DFA (Deterministic Finite Automaton). This conversion is known as the subset construction or powerset construction.

The subset construction algorithm allows us to construct a DFA that recognizes the same language as a given NFA. Therefore, for any NFA, it is always possible to construct a DFA that accepts the same language.

Hence, the correct answer is 3. There are no NFAs for which no DFA can be constructed.

ac ∈ L(r₁), since we can take b* as ∈ and c* as c. ac ∈ L (r₃), since (a + b + c ) * includes all combinations of a, b and c.
ac ∉ L(r₂) since whenever (a * b + c)* is taken to include a, “a is always followed by b".
a*b = b, ab, aab, .... & so on.

L(r₁) is the set of all string starting with ‘a’.
L(r₂) is the set of all starting with ‘b’.
Since any word belonging to ∑* either starts with “ a ” or starts with " b ” or is “∈ ” , therefore 

Note that
  gives all the combinations of a and b followed by all the combinations of c and d, for  
will generate all strings with combination of a, b, c, b and d.

As we can construct the DFA for the given languages, hence all of the given languages are regular.

Explanation:
A regular expression describes the language over some alphabet.
(i) aa: This regular expression matches the strings "aa" only. It does not cover the cases where there are b's in between or around the a's. So, it does not represent all strings over the alphabet {a, b} that contains exactly two a’s.
(ii) ab*a: This regular expression matches strings like "aa", "aba", "abba", etc. It allows for zero or more b's between two a's and hence, it corresponds to the language of all strings over the alphabet {a, b} that contains exactly two a’s.
(iii) b*ab*a: This regular expression matches strings like "aa", "aba", "abba", "baa", "baba", etc. It allows for zero or more b's before, between, and after two a's and hence, it corresponds to the language of all strings over the alphabet {a, b} that contains exactly two a’s.

Therefore, only (ii) and (iii) correctly represent the language of all strings over the alphabet {a, b} that contains exactly two a’s.

The correct answer is  (ii) and (iii) only.
 

Choice ‘a’ is incorrect since it does not include the string “a”, “b” and "∈” (all of which do not end with ab).
None of choices 'c' or ‘d ’ accept the string ‘a ’, So they can’t represent specified language.

The regular expression corresponding to the language of strings of even lengths over the alphabet of {a, b} is ((a + b)²)* which is equivalent to (aa + bb + ba + ab)*. In choice (b) the string ‘ab’ is not present. In choice (c) the string ‘aa’ is not present. In choice (d) odd length strings are also acceptable.

For DFA accepting all the strings with number of a’s divisible by 4; four states are required similarly for DFA accepting all the strings with number of b’s divisible by 5, five states are required and for their combination, states will be multiplied. So 5 x 4 = 20 states will be required.