Register

GO Classes DPP | GATE CS | Theory of Computation | Closure Properties

• edited by
87 views
0 0 votes

Let $X$ and $Y$ be regular languages. Their symmetric difference is

$$X\triangle Y=\{w:w\text{ belongs to exactly one of }X,Y\}$$. Which expression correctly represents $X\triangle Y$ and proves that it is regular?

  1. $(X\cap Y)\cup(\overline X\cap\overline Y)$
     
  2. $(X\cap\overline Y)\cup(\overline X\cap Y)$
     
  3. $\overline{X\cup Y}$
     
  4. $X\cap Y$

1 Answer

1 1 vote

A string belongs to the symmetric difference when:

  • it is in $X$ but not $Y$, or
     
  • it is in $Y$ but not $X$.

Therefore, $$X\triangle Y = (X\cap\overline Y) \cup (\overline X\cap Y)$$Regular languages are closed under:

$$\text{complement},\qquad \text{intersection},\qquad \text{union}$$Hence $X\triangle Y$ is regular.

• edited by
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

2 2 votes
1 1 answer
106
106 views
GO Classes asked Sep 21
106 views
GO Classes DPP | GATE CS | Theory of Computation | Language Quotient
For languages $X,Y\subseteq\Sigma^*$, define$$X/Y = \{w:\exists y\in Y,\ wy\in X\}$$ Suppose $X$ is regular, but nothing is assumed about $Y$.Which statement is always tr...
2 2 votes
1 1 answer
91
91 views
GO Classes asked Sep 21
91 views
GO Classes DPP | GATE CS | Theory of Computation | Regular Language
Let $M$ and $N$ be two DFAs. Define$$Z=\{u_1v_1u_2v_2\cdots u_kv_k : k\ge0, ~u_i\in L(M), ~v_i\in L(N)\}.$$Which regular-language expression describes $Z$?$L(M)^*L(N)^*$ ...
0 0 votes
1 1 answer
73
73 views
GO Classes asked Sep 21
73 views
GO Classes DPP | GATE CS | Theory of Computation | Regular Language
For an arbitrary language $L$, which of the following statements is correct?If $L^*$ is regular, then $L$ must be regular. If $L$ is nonregular, then $L^*$ must be nonreg...
2 2 votes
1 1 answer
126
126 views
GO Classes asked Sep 19
126 views
GO Classes DPP | GATE CS | Theory of Computation | Closure Properties
Let $L_1$ and $L_2$ be regular languages and let $L_3$ be non-regular. Which statements are always true?$L_1=L_2$ iff $L_1\cap\overline{L_2}=\emptyset$ $L_1\cup L_3$ is n...