16. Which one of the following is NOT a valid identity?

- Option : B
- Explanation :

(a) x ⊕ y = (xy + x′y ′)′

= (xy )′

= x ⊕ y, it is valid.

(b) (x + y) ⊕ z = (x + y).z + (x + y)z

= xyz + xz + yz

= 1 4,6 2,6

= Σm(1, 2, 4, 6)

(x + y) ⊕ z = x(y+z) + x (y+z)

= xy + xz + yz

= 2,3 1,3 4

= Σm(1, 2, 3, 4)

(x + y) ⊕ z ≠ x ⊕ (y + z)

So option (b) is invalid.

(c) (x ⊕ y) ⊕ z = x ⊕ (y ⊕ z)

Associativity is true on Ex-OR operator so it valid.

(d) x ⊕ y = (x + y)(x + (y)

= (x + y)xy

= (x + y)x0

= (x + y), so it is valid.

You must be logged in to post a comment.

17. If 𝐿 is a regular language over Σ = {𝑎,}, which one of the following languages is NOT regular?

- Option : B
- Explanation :

If L is regular, L.L^{R}is also regular by closure property.

Suffix (L) and Prefix (L) are also regular by closure property.

However option (b) {ww^{R}|w∈L} need not be regular since if L is an infinite regular language, then {ww^{R}|w ∈ L} will not only be infinite, but also non-regular. Since it involves string matching and we can increase in length indefinitely and then finite automata FA will run out of memory.

You must be logged in to post a comment.

You must be logged in to post a comment.

- Option : D
- Explanation :

Both I and II are equivalent statements.

You must be logged in to post a comment.

You must be logged in to post a comment.

- Option : B
- Explanation :

Given**R**is a equivalence relation, because it satisfied reflexive, symmetric, and transitive conditions:_{1}**Reflexive:**a = g^{–1}ag can be satisfied by putting g = e, identity “e” always exists in a group.**Symmetric:**

aRb ⇒ a = g^{–1}bg for some g

⇒ b = gag^{–1}= (g^{–1})^{–1}ag^{–1}

g^{–1}always exists for every g ∈ G.**Transitive:**

aRb and bRc ⇒ a = g1^{–1}bg1

and b = g2^{–1}cg2 for some g1g2 ∈ G.

Now a = g1^{–1}g2^{–1}cg2g1 = (g2g1)^{–1}cg2g1

g1 ∈ G and g2 ∈ G ⇒ g2g1 ∈ G since group is closed so aRb and aRb ⇒ aRc

**R**is not equivalence because it does not satisfied reflexive condition of equivalence relation:_{2}

aR_{2}a ⇒ a = a^{–1}∀a which not be true in a group.

So, option (B) is correct.

You must be logged in to post a comment.

You must be logged in to post a comment.

You must be logged in to post a comment.