a set of strings all of which are chosen from some , where is a particular alphabet, is called a language. if is an alphabet, and , then is a language over . notice that a language over need not include strings with all the symbols of , so once we have established that is a language over , we also know it is a language over any alphabet that is a superset of .
since languages are sets, set operations are applicable to them.
, the reverse of is defined by , where denotes the reverse of the word .
prove/disprove
counter example for 1:
proof for 2:
given , we define recursively by .