Cheap and Secure Web Hosting Provider : See Now

[Solved]: Concatenation property of regular languages

, , No Comments
Problem Detail: 

If L is the empty set and therefore a regular language, I know that L concatenated with sigma star is equal L; Are there any other languages that, when concatenated with sigma star will result in the same language?

Asked By : O.A.

Answered By : Patrick87

$L \Sigma^* = \emptyset \Sigma^* = \emptyset = L$

$\Sigma^*L = \Sigma^* \emptyset = \emptyset = L$

$L \Sigma^* = (S \Sigma^*)\Sigma^* = S \Sigma^* = L$ for all languages $S$

$\Sigma^* L = \Sigma^* (\Sigma^* S) = \Sigma^* S = L$ for all languages S

$L \Sigma^* = (\Sigma^* S \Sigma^*) \Sigma^* = \Sigma^* S \Sigma^* = L$ for all languages $S$

$\Sigma^* L = \Sigma^* (\Sigma^* S \Sigma^*) = \Sigma^* S \Sigma^* = L$ for all languages S.

In short: there are infinitely many distinct languages where appending the language to $\Sigma^*$ (front or back) will yield the same language. An infinite family of such languages is given by $\Sigma^* S \Sigma^*$ where $S$ can be any language whatsoever.

Best Answer from StackOverflow

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

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback