Languages
Alphabet, Word
An alphabet
A finite sequence of symbols or letters (string) is also called a word over
The set of all words over
The set of all non-empty words over
Length of a word
Let
The length of
Note that
Concatenation of words
Let
The concatenation of
Subword
Two words over
A word
Prefix, Suffix
A word
A word
Reversal (mirror image)
The reversal or mirror image of a word
For
Power of a word
Let
The power of
By convention,
Language
For an alphabet
The empty language is denoted by
A language is finite if it contains a finite number of words, and infinite otherwise.
Occurrence of symbols
Notation
Operations on languages
Let
Union
The union of
Meaning that
Intersection
The intersection of
Meaning that
Difference
The difference of
Can also be denoted by
Meaning that
Complement
The complement of
Meaning that
Reversal
The reversal of
Meaning that
Concatenation
The concatenation of
Meaning that
Power
The power of
Meaning that
Note that
Closure
The closure of
Meaning that
Positive closure
The positive closure of
Meaning that
Note that
Prefix
The prefix of
Meaning that
Suffix
The suffix of
Meaning that
Homomorphism
A homomorphism is a function
Image of a language
The image of a language
Meaning that
Example 1
Let
Find
Solution
Prefixes of
Suffixes of
Example 2
Let
Find
Solution
Example 3
Let
Find
Solution
Example 4
Let
Find
Solution
Example 5
Let
Find
Solution
Example 6
Let
Find
Solution
Example 7
Let
Find
Solution
Example 8
Let
Find
