The given language is not CFL ,it is CSL and CFL is not closed under complement operation ,Now I am not getting how to find it's complement ,please tell the approach .
Asked
Active
Viewed 2,663 times
0
-
Are you trying to describe the language, or are you trying to determine where it falls in the hierarchy (regular, context-free, context-sensitive, unrestricted)? – Brian M. Scott Dec 24 '15 at 21:25
-
I am not getting how to find the complement of this CSL . – Radha Gogia Dec 25 '15 at 03:20
1 Answers
1
Let $L'$ be the complement, $L'=\{a,b\}^*\setminus L$. Clearly every word in $L$ has even length, so every word of $\{a,b\}^*$ with odd length must be in $L_1$. Let
$$R=\left\{w\in\{a,b\}^*:|w|\text{ is odd}\right\}\;;$$
then $R\subseteq L_1$.
It remains to determine what word of even length are in $L_1$. These are precisely the words in $\{a,b\}^*$ that can be written in the form $uv$, where $u\ne v$ and $|u|=|v|$. Thus
$$L_1=R\cup\left\{uv\in\{a,b\}^*:u\ne v\text{ and }|u|=|v|\right\}\;.$$
Brian M. Scott
- 616,228
-
will the grammar for L1 be like S-->A0A / B1B , A-->1A , B -->0B so that u≠v and |u|=|v| – Radha Gogia Dec 25 '15 at 03:32
-
@Radha: I’ve not tried to prove it, but I strongly suspect that $L_1$ is not context free. (It definitely is at least context-sensitive.) Your proposal definitely does not generate $L_1$, or even $L_1\setminus R$. – Brian M. Scott Dec 25 '15 at 03:34
-
I was talking only about second part in which we have {uv∈{a,b}*:u≠v and |u|=|v|}. – Radha Gogia Dec 25 '15 at 03:35
-
@Radha: Yes, $L_1\setminus R$. But if you experiment a bit, you’ll find that your grammar doesn’t generate that language. – Brian M. Scott Dec 25 '15 at 03:36
-
yes you are right so then how to make both the length of u and v same ? – Radha Gogia Dec 25 '15 at 03:39
-
@Radha: I can see how to build a context-sensitive grammar that would do the job, but the details would be a pain to work out. – Brian M. Scott Dec 25 '15 at 03:42
-
@brian-m-scott It looks like $L_1$ is context-free. See Show that ${ xy \mid |x| = |y|, x \not= y }$ is context-free – J.-E. Pin Feb 01 '16 at 18:47
-
@J.-E.Pin: Thanks; I rather thought so but was too lazy to work out the details, since it wasn’t needed. Raphael’s grammar is a lot neater than the approach that I had in mind. – Brian M. Scott Feb 01 '16 at 21:17