edited by
728 views
3 votes
3 votes

Let $L_1$ and $L_2$ be two arbitrary languages, choose incorrect statement(s)

  1. $\text{if}\; L_1.L_2\;\text{ is regular then }L_2.L_1\;\text{ is also regular.}$
  2. $L_1 = L_2 \;\text{iff}\; L_1 \backslash L_2 = \phi \; \text{and}\; L_2 \backslash L_1 = \phi .$
  3. $\text{if}\; L\subseteq \Sigma^* \;\text{and}\; L\; \text{is finite, then}\; \Sigma^* \backslash L \;\text{is regular}$ (\ denotes set difference)
  1. Only (i)
  2. (i) and (ii)
  3. (ii) and (iii)
  4. All
 
edited by

1 Answer

Best answer
16 votes
16 votes

$L_1$ and $L_2$  are two arbitrary languages

Option 1. $\text{if}\; L_1.L_2\;\text{ is regular then }L_2.L_1\;\text{ is also regular}$

Let $L_1=\{a^p \; \mid \; \text{p is prime}\}$, and $L_2=\{a^nb^m \; \mid \; m,n\geq 0\}$

then  $L_1.L_2=\{a^ib^j \; \mid \; i\geq 2,j\geq 0\}$ is Regular.

and $L_2.L_1=\{a^ib^ja^p \; \mid \; i,j\geq 0,\text{p is prime}\}$ is Non-regular.

 
Option 2. $L_1 = L_2 \;\text{iff}\; L_1 \backslash L_2 = \phi \; \text{and}\; L_2 \backslash L_1 = \phi$
 

$L_1 \backslash L_2 = \phi$ means all strings of $L_1$ are present in $L_2$ , and

 $L_2 \backslash L_1 = \phi$ means all strings of $L_2$ are present in $L_1$ 

option3. $\text{if}\; L\subseteq \Sigma^* \;\text{and}\; L\; \text{is finite, then}\; \Sigma^* \backslash L \;\text{is regular}$

$L$ is finite, means $L$ is regular , so $\Sigma^* \backslash L = \Sigma^* - L $ is also regular 

Only i) is incorrect

selected by

Related questions

1 votes
1 votes
2 answers
1
aditi19 asked Mar 24, 2019
621 views
If $L = \Bigl \{ x \mid x \in \{ a, b, c \}^*, \text{The length of $x$ is a square } \Bigr \}$ then $L$ isRegularRecursive but not context freeContext Free but not regula...