The symmetric difference of two sets \(S_1\) and \(S_2\) is defined as \(S_1…
2016
The symmetric difference of two sets \(S_1\) and \(S_2\) is defined as
\(S_1 \oplus S_2 =\{x \mid x \in S_1 \text{ or } x \in S_2, \text{ but x is not in both } S_1 \text{ and } S_2 \}\)
The nor of two languages is defined as
\(nor(L_1, L_2)=\{w \mid w \notin L_1 \text{ and } w \notin L_2 \}\)
Which of the following is correct ?
- A.
The family of regular languages is closed under symmetric difference but not closed under nor.
- B.
The family of regular languages is closed under nor but not closed under symmetric difference.
- C.
The family of regular languages are closed under both symmetric difference and nor.
- D.
The family of regular languages are not closed under both symmetric difference and nor.
Attempted by 55 students.
Show answer & explanation
Correct answer: C
Reasoning: Use closure properties of regular languages to rewrite each operation.
Symmetric difference: L1 ⊕ L2 = (L1 ∩ complement L2) ∪ (complement L1 ∩ L2).
Since regular languages are closed under intersection, union, and complement, the symmetric difference of two regular languages is regular.
Nor: nor(L1, L2) = { w | w ∉ L1 and w ∉ L2 } = complement(L1 ∪ L2).
Because regular languages are closed under union and complement, nor of two regular languages is regular.
Conclusion: The family of regular languages is closed under both symmetric difference and nor.
A video solution is available for this question — log in and enroll to watch it.