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

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₁ = (ab*ba*) and L₂ = (ba*ab). The string in L₁ should always start with ‘a’, where as for L₂ 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₁ must end with ‘b ’, where a s strings in L₂ must end with ‘a’.

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.

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.

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.

A language over an alphabet R is a set of strings over A which is uncountable and infinite.
Correct answer is D.

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)*

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.

The given grammar is right linear.

The above FA accepts the language
L(G) = aa* bb* cc*

The regular expresession for the language:
L = {W | W does not contain 3 consecutive 0 ’s} is 

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

Clearly, we can observe that the minimum string accepted is,aabb.
The corresponding L(M) = { w | w∈ (a + b)* aabb (a + b)*}.

Regular grammar is a subset of context free grammar.

r₁, denotes multiple of 3 a’s, with any number of b’s.
r₂ denotes multiple of 2 a’s, with any number of b’s. L(r₁) ∩ L(r₂) denotes multiple of 6 a’s, with any number of b’s. Hence,

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