Cheap and Secure Web Hosting Provider : See Now

What is the complement of the language with all ucv with u ≠ v?

, , No Comments
Problem Detail: 

If $L = \{w_1cw_2: w_1,w_2 \in \{a,b\}^* , w_1 \neq w_2\}$ what is the complement of language L? one of my friend said that it is $\overline{L} = \{w_1cw_2: w_1,w_2 \in \{a,b\}^* , w_1 = w_2\}$ and he said that we can ignore $c$ and it's not in $\Sigma$ of language $L$. but I think $c$ should be in $\Sigma$ of language $L$ and the complement mentioned above is wrong based on definition of complement that is $\{a,b,c\}^* \backslash L$. which answer is right?

Based on transition relation of pushdown automata where is maping from $(Q\times (\Sigma \cup \{\lambda \}) \times \Gamma) $ to $(Q \times \Gamma^*)$ so if we construct a pushdown automata for string $aabcabb$ for example here $c$ should be in $\Sigma \cup \{\lambda \}$.

Asked By : Karo
Answered By : Yuval Filmus

The complement of a language $L$ over an alphabet $\Sigma$ consists, by definition, of all words over $\Sigma$ that are not in $L$. If you use this definition, you find out that $\overline{L}$ consists of all words of the form $wcw$ for $w \in \{a,b\}^*$ (like your friend said), as well as all words which contain either no $c$ or at least two $c$s.


The complement operation for languages, like the complement operation for sets, assumes an underlying universe. In the case of languages, the underlying universe is $\Sigma^*$, where $\Sigma$ is the alphabet that the language is defined over. You an think of languages in at least two ways:

  • A language is a pair consisting of an alphabet $\Sigma$ and a subset of $\Sigma^*$. We usually only explicitly mention the second part.

  • A language is a collection of "words" over some universal alphabet. We can think of the language as being over any alphabet which includes all the symbols appearing in the language.

While the more correct view is the first, the more practical view is the second. Therefore, whenever you take the complement of a language, you must make sure with respect to which alphabet the complement is taken. This can be done in at least two ways:

  • When you define the language, you also mention the underlying alphabet.

  • When you take the complement, you state with respect to which alphabet you are complementing it.

For example, you could say:

Let $L$ be the language over $\{a,b,c\}$ given by $L = \{ w_1 c w_2 : w_1,w_2 \in \{a,b\}^* \text{ and } w_1 \neq w_2 \}$. What is the complement of $L$?

Or you could say

Let $L = \{ w_1 c w_2 : w_1,w_2 \in \{a,b\}^* \text{ and } w_1 \neq w_2 \}$. What is the complement of $L$ (as a language over $\{a,b,c\}$)?

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/56648

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback