edited by
2,490 views
9 votes
9 votes

Consider the following languages $L_1$ and $L_2$

  • $L_1=\{a^mb^n\, |\, m,n\geq 0 \}$
  • $L_2=\{a^mb^n\, |\, m=n \}$


if$(L_1\cup\overline{L_2})=L$ then what is the language $L$?


a. $L=\{a^mb^n\, |\, m,n\geq 0 \}$
b. $L=\{a^mb^n\, |\, m !=n \}$
c. $L=(a+b)^*-\{a^nb^n\}$
d. $L=(a+b)^*-\{a^mb^n \, | \, m!=n\}$

edited by

4 Answers

Best answer
17 votes
17 votes

Say, $A$ is universal set , $A=\Sigma^* =(a+b)^*$

It is clear that $L1$ is subset of $A$, and $L2$ is subset of $L1$.

it is clear from the diagram that $L1 \cup\overline{L2} = L =\Sigma^{*} =(a+b)^{*}$

Note :

 It is very often to see, that we thought  $\overline{L2}$ = $\overline{\{ a^mb^n |m =n\}}$= {$a^mb^n |m\neq n$} but remember $\overline{L2}$ also contain simple $a$, or $a^*$ or $b^*$ or $b^*a^*$ or strings as $aba$ or many things.

Actually $\overline{L2}=\Sigma^* -\{a^nb^n\}$
 

selected by
2 votes
2 votes

Ans will be (ambn m,n>=0) ⋃ (bm an m≠ n)   //since both said a should come first then b come.

most aprropriate is a

1 votes
1 votes

regular ⋃ (DCFL)'

=regular ⋃ DCFL (DCFL closed under complement)

=regular(union means all language will be within that resulting language)

Here a*b*⋃(ambn where m!=n )

i.e. a*b* ⋃ (∑* - an bn) =a*b*

which is (A)

edited by
0 votes
0 votes

 Σ= (a+b)*   - anbn = {anbm m!=n} ∪ { (a+b)*  ba (a+b)*

L2' =   {anbm m!=n} ∪ { (a+b)*  ba (a+b)*

L1 U L2 = (a*b*) U {anbm m!=n} ∪ { (a+b)*  ba (a+b)* }  = (a*b*) U { (a+b)*  ba (a+b)*

Correct Answer

Related questions

5 votes
5 votes
2 answers
1
radha gogia asked Nov 29, 2015
1,499 views
If I take L=a^n b^n and R=(a+b)* so I am getting the value of L/R to be regular ,Am I correct ?
0 votes
0 votes
3 answers
2
HenryAsks21 asked Mar 4, 2022
1,419 views
For the following question if True show why, and if it’s False show why.)Question: For any language A1, A2, if $A1 \cup A2$ is regular, then A1 and A2 are regular langu...