patternMinor
Concatenation property of regular languages
Viewed 0 times
languagespropertyconcatenationregular
Problem
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?
Solution
$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.
$\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.
Context
StackExchange Computer Science Q#25798, answer score: 4
Revisions (0)
No revisions yet.