Description

This mock test of Finite Automata: Regular Languages (Advance Level) - 1 for Computer Science Engineering (CSE) helps you for every Computer Science Engineering (CSE) entrance exam.
This contains 15 Multiple Choice Questions for Computer Science Engineering (CSE) Finite Automata: Regular Languages (Advance Level) - 1 (mcq) to study with solutions a complete question bank.
The solved questions answers in this Finite Automata: Regular Languages (Advance Level) - 1 quiz give you a good mix of easy questions and tough questions. Computer Science Engineering (CSE)
students definitely take this Finite Automata: Regular Languages (Advance Level) - 1 exercise for a better result in the exam. You can find other Finite Automata: Regular Languages (Advance Level) - 1 extra questions,
long questions & short questions for Computer Science Engineering (CSE) on EduRev as well by searching above.

QUESTION: 1

Which of the following statements are true?

Solution:

For (i) intersection of (ab)*(ba)* and (ba)*(ab)* is not {∈}. For eg. “ab” is one more string which satisfies '∩'.

Therefore (ii) is false.

For (ii) let L_{1} = (ab*ba*) and L_{2} = (ba*ab). The string in L_{1} should always start with ‘a’, where as for L_{2} it always starts with ‘b'. ∈ is not part of either language. Hence intersection is {}.

Hence (ii) is also false.

For (iii) both (a*b*b)* and (b*a*a)* contain “∈".

No other string is common. Because strings in L_{1} must end with ‘b ’, where a s strings in L_{2} must end with ‘a’.

QUESTION: 2

Which of the following statements are true?

Solution:

The first one is not ∑* because ‘aa’ is not present in the language L in (ii) all possible strings are present since, (a*b*)'= (a*+ b*)* = (a + b)* Therefore (ii) is ∑*. (iii) is not ∑* because, in (iii) single letter strings ‘a’ or ‘b’ are not present. Also abba, aa, bb, etc. are also not present.

QUESTION: 3

If a DFA is represented by the following transition table, then how many states does the corresponding minimal DFA contains?

Solution:

Drawing the DFA corresponding to the given transition table:

Use DFA minimization algorithm

The corresponding minimum state DFA for this language can be constructed as

Only 4 states are needed.

QUESTION: 4

Consider G = {(a, b), {S}, S, |S→b|Sa|aS|SS}) Which of the following are true?

(i) aabbaa ∈ G

(ii) G is ambiguous

(iii) Regular expression corresponding to G is ba*

Solution:

Two derivation trees are possible for aabba as given below:

Therefore (i) and (ii) are both true.

Choice (iii): ‘aba’ is also accepted by the given grammar. Therefore (iii) is false.

QUESTION: 5

Which languages does the following DFA accept?

Solution:

We can clearly see that any number of loops of "ab” and "bb” can be accepted and ‘0’ is the accepting state.

QUESTION: 6

Which of the following statements are false?

Solution:

The given regular expression 00(1 + 10)* is not complete to denotes all strings of 0’s and 1 ’s with atleast two consecutive 0’s.

The correct regular expression must be

(0 + 1)* 00(0 + 1)*

QUESTION: 7

Which of the following statement must always be true for A and B? Suppose A and B are two sets of strings from ∑*, such that

(i) if A is finite then, B is finite.

(ii) If A is regular then, S is regular.

(iii) If A is context free then, B is context free,

Solution:

it is possible to have a subset of regular language which is not regular and a subset of CFL which is not CFL, but a subset of finite set has to be finite.

For example:

Hence, (ii) and (iii) are incorrect.

QUESTION: 8

Consider the following grammar G:

Which of the following is L(G)?

Solution:

The given grammar is right linear.

The above FA accepts the language

L(G) = aa* bb* cc*

QUESTION: 9

Deterministic finite automata of a language over alphabets {0, 1), which does not contain 3 consecutive 0’s. Minimum how many states, S, in all, the DFA will have and how many of them will be final states, F?

Solution:

The regular expresession for the language:

L = {W | W does not contain 3 consecutive 0 ’s} is

QUESTION: 10

Consider the following regular grammar:

Minimized deterministic finite automata of which R_{1}, R_{2} and R_{3} are exactly same except state names?

Solution:

Clearly from (1), (2) and (3).

QUESTION: 11

Consider the following machine M:

What is the language L(M) accepted by this machine?

Solution:

Clearly, we can observe that the minimum string accepted is,aabb.

The corresponding L(M) = { w | w∈ (a + b)* aabb (a + b)*}.

QUESTION: 12

Consider a grammar G as follows:

Solution:

The given grammar G:

Then S → aA generates {ab^{2n}c, n ≥ 0} then the language corresponding to it is

So, L(G) = {ab^{2n}c| n≥ 0}

QUESTION: 13

Let r_{1} = (a + b^{2})*, r_{2} = (a* + b*)*, r_{3} = (a^{2} + b)*. Which of the following is true?

Solution:

QUESTION: 14

r_{1} = {b* ab* ab* ab*)*, r_{2 =} (b* ab* ab*)*. What is L(r_{1}) ∩ L(r_{2})?

Solution:

r_{1}, denotes multiple of 3 a’s, with any number of b’s.

r_{2} denotes multiple of 2 a’s, with any number of b’s. L(r_{1}) ∩ L(r_{2}) denotes multiple of 6 a’s, with any number of b’s. Hence,

QUESTION: 15

Which of the following statement is not correct?

Solution:

Since L is accepted by TM, which halts on every W in L, it is recursive. The complement must also be than recursive.

### Regular Expressions And Finite Automata

Doc | 20 Pages

### Finite Automata

Doc | 6 Pages

### Finite Automata

Doc | 1 Page

### Finite Automata

Video | 11:05 min

- Finite Automata: Regular Languages (Advance Level) - 1
Test | 15 questions | 45 min

- Finite Automata: Regular Languages (Basic Level) - 1
Test | 10 questions | 30 min

- Regular Expressions And Finite Automata Practice Quiz - 1
Test | 20 questions | 60 min

- Test: Finite Automata And Regular Expressions
Test | 15 questions | 15 min

- Regular Expressions And Finite Automata Practice Quiz - 2
Test | 20 questions | 60 min