Theory of Computation Test 2

Option 1: (00 + (11)*0)

This regular expression generates the strings like:

{0, 00, 000, 110, 11011, 11110, 11000, …} .

It is not generating 1101 because after every 11 there is a single 0 possible but a single 1 is not possible in any case.

Option 2: 1(0 + 1)*101

It is generating strings of type: {1101, 10101, 11101, 101101, ………}.

It contains the string 1101, so not the correct answer.

Option 3: (10)* (00 + 11)* (01)*

This regular expression is generating strings of type: {ϵ, 10, 00, 11, 01, 1000, 1011, 1001, 1101…….}.

It is possible to get 1101 in this expression. So, it is the not correct answer.

Option 4: 110*(0 + 1)

In this, set of strings that are possible are: {110, 111, 1100, 1101, 11001,……..}.

So it is generating the string 1101. So, it is not the correct answer.

Concept:

We will solve the above equation R = Q + RP using Arden’s Theorem

Explanation-

In order to find out a regular expression of a Finite Automaton, we use Arden’s Theorem along with the properties of regular expressions.

Statement

Let P and Q be two regular expressions.

If P does not contain null string, then R = Q + RP has a unique solution that is R = QP*

Proof:

R = Q + (Q + RP) P [After putting the value R = Q + RP]

= Q + QP + RPP

When we put the value of R recursively again and again, we get the following equation −

R = Q + QP + QP² + QP³…..

R = Q (ε + P + P² + P³ + ….)

R = QP* [As P* represents (ε + P + P² + P³ + ….)]

Concept:

Two regular expression are equivalent if languages that are generated by them are also equal.

Explanation:

Given regular expression: (r₁ + r₂)*

It means 0 or any sequence of r₁ and r₂

Check all the options one by one:

Option 1: r₁* r₂*

In this it can generate any no. of r₁ and r₂. But r₁ is followed by r₂.

Option 2: (r₁r₂)*

It generates all the strings in which r₁r₂ are together. It generates any number of r₁r₂.

We cannot generate single r₁ and r₂.

Option 3: r₁*r₂* + r₁r₂

It cannot generate the same language as that of given regular expression. It cannot generate null string.

Option 4: (r₁*r₂*)*

It is equivalent to (r₁ + r₂)*. It can generate null string and any combination of r₁ and r₂. Hence it is equal to the given regular expression.

(i) ((01)*(10)*)*

It generates the strings of type {ϵ, 01, 10, 0110, 0101, 1001, 1010, 010110, 01011010,……..}

(ii) (10 + 01)*

Set of strings that are generated by the regular expression:

{ ϵ , 10, 01, 1010, 0101, 0110, 1001, 101010, 010101,………..}

(iii) (01)* + (11)*

Strings that are generates with this expression are:

{ ϵ , 01, 11, 0101, 1111, 010101, 111111,………. }

(iv) (0* + (11)* + 0*)*)

Strings that are generated with this regular expression:

{ ϵ , 0, 11, 00, 000, 011, 110, 0110, 00110, 01100,……….}

Regular expression of first two options are equal, both these regular expressions generate same set of strings.

Concept: Property of context-free languages is:

Context-free languages are closed under union and difference but not closed under complementation and intersection.

Explanation:

Option 1) M – X is context-free

As a difference of a context-free language with regular is context-free. So, it is correct.

Option 2) L ∪ M is context-free

As context-free languages are closed under union. So it is correct.

Confusion Point:

If two languages are context-free language, then it is not closed under set difference operation, but if one language is regular and other is context-free than it is closed under set difference operation.