Skip to main content
3 of 3
added 123 characters in body
Vor
  • 12.7k
  • 1
  • 30
  • 62

Another quick solution: use two letters ($\Sigma = \{a,b\}$) and use $b$ only as a separator, then make $L$ irregular using a counting argument in such a way that in $L \cup L^R$ the counting argument "disappears" ...

Solution:

if $L = \{a^nba^m | n \geq m \}\;$, then $L^R =\{a^nba^m | n < m \} $
and therefore $L \cup L^R = \{a^*ba^*\}$

If your professor complains that there are too few $b$s out there (a cheat :-), then $L = \{a^nb^pa^m | n \geq m \}$ works equally well.

Vor
  • 12.7k
  • 1
  • 30
  • 62