Test: Finite Automata: Regular Languages- 1

QUESTION: 1

Which of the following is false?

A.
The languages accepted by FA’s are regular languages.
B.
Every DFA is an NFA.
C.
There are some NFA’s for which no DFA can be constructed.
D.
If L is accepted by an NFA with ∈ transition then L is accepted by an NFA without ∈ transition.

Solution:

For every NFA there exist an equivalent DFA and vice-versa. Power of both NFA and DFA for recognization of language is same.

QUESTION: 2

Let r₁= abcand r₂= (ab+c)and r₃= (a+b+c)*. Then which of the following is true

A.
w = ’ac’ belongs to L(r₂) and L(r₃) but not L(r₁)
B.
w = 'ac' belongs to L(r₃) only
C.
w = 'ac' belongs to L(r₁), L(r₂) and L(r₃)
D.
w = ‘ac’ belongs to L(r₁) and L(r₃) but not L(r₂)

Solution:

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.

QUESTION: 3

Let ∑ = {a, b}, r₁ = a(a + b)* and r₂ = b(a + b)*. Which of the following is true?

A.
L(r₁) = L(r₂) = ∑*
B.
L(r₁) ∩ L (r₂) = {∈}
C.
L(r₁) ∪ L(r₂) = ∑*
D.
L(r₁) ∪ L(r₂) ∪ {∈} = ∑*

Solution:

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

QUESTION: 4

Which of the following statements are true?
(i) abcd ∈ L((b*a*)* (d*c*)*)
(ii) abcd ∈ L((d*c*b*a*)*)
(iii) abcd ∈ L((a*b*a*c*d*)*)

A.
(i) and (iii) only
B.
(ii) and (iii) only
C.
(i) and (ii) only
D.
All of these

Solution:

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.

QUESTION: 5

Which of the following are regular languages?
(i) The language  w has an odd number of b’s}.
(ii) The language  w has an even number of b’s).
(iii) The language  has an even number of b’s and odd number of a’s).

A.
(i) and (ii) only
B.
(i) only
C.
(ii) only
D.
All of these

Solution:

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

QUESTION: 6

Which of the following regular expression corresponds to the language of all strings over the alphabet {a, b) that contains exactly two a’s
(i) aa
(ii) ab*a
(iii) b* ab*a

A.
(i) arid (ii) only
B.
(ii) and (iii) only
C.
(i) and (iii) only
D.
None of these

Solution:

All languages are accepting strings over the alphabet {a, b} that contains exactly two a’s but they are not accepting all strings like the first choice just accepts ‘aa’. The second choice can’t accept ‘baa’. The third choice can’t accept ’baab’. The correct regular expression is b* a b* a b*.

QUESTION: 7

Which of the following regular expression corresponds to the language of all strings over the alphabet {a, b} that do not end with ab?

A.
(a + b)* (aa + ba + bb)
B.
(a + b)* (aa + ba + bb) + a + b + ∈
C.
b* ab*
D.
b* aa b*

Solution:

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.

QUESTION: 8

What is regular expression corresponding to the language of strings of even lengths over the alphabet of {a, b}?

A.
(aa + bb + ba + ab)*
B.
(aa + bb)*
C.
(ab + bb + ba)*
D.
a*b*a*b*

Solution:

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.

QUESTION: 9

How many minimum number of states are required in the DFA (over the alphabet {a, b}) accepting all the strings with the number of a’s divisible by 4 and number of b’s divisible by 5?

A.
20
B.
9
C.
7
D.
15

Solution:

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.

9 Questions MCQ Test Question Bank for GATE Computer Science Engineering | Test: Finite Automata: Regular Languages- 1

Which of the following is false?

Let r₁= abcand r₂= (ab+c)and r₃= (a+b+c)*. Then which of the following is true

Let ∑ = {a, b}, r₁ = a(a + b)* and r₂ = b(a + b)*. Which of the following is true?

Recommended Content

Representation of Basic Information

Proposition and Logical Connectives

Recursion

Recursive Function Theory

Machine Instructions & Addressing Modes

Recommended Tests

Test: Arrays, Stack, Queues & Linked List- 1

Test: Software Engineering- 1