The elements

• an alphabet - arbitrary set of characters e.g. S = { a b } or { a, b}
• a language over this alphabet - an arbitrary set of strings called words to be formed from the alphabet
• e.g. L = { abb, aba, b }
• the special string of no letters is called the null string, and denoted by L or l , (the Greek letter "lambda")
• the string "xxx . . . x" of n x's, will be abbreviated to xⁿ

• If S is an alphabet, all the words (including l ) that can be formed using 0 or more letters from S (any letter may be used multiple times) is called the Kleene closure of S , and is denoted by S^*
• If at least one character must be used, we generate a language that does not include l , denoted by S⁺, referred to as the positive closure.

If L is a language, all the words (including l ) that can be formed from L (same process as for forming Kleene closure from a vocabulary) is called the Kleene closure of L, and is denoted by L^*.  Similarly for L⁺.  If L contains l , then L⁺ contains l , otherwise not.

Palindromes

If w is a word, then reverse(w) is w with the letters reversed. Any word w such that w = reverse(w) is a palindrome. E. g. "able was I ere I saw elba" (this is a word that includes space as a character).

Factoring (or parsing)

L = { aba, aa, ba }.  Question: is w = abaabaaaba in L* ?
w can be factored as follows: (aba)(aba)(aa)(ba).  Notice that each "factor" is a word in L.  (This factorization proves that w is in L^*)

Example: you have seven people from which to select a committee of three. How many different committees?
Ans: the combinations of 7 things chosen 3 at a time. Mathematically:
"7 choose 3"  =  ₇C₃  =   =  35

Christmas tree lights problem:
7 red lights, 3 green lights, 4 blue lights. How many different distinguishable strings of 14 lights are there?

Solution:
place the red lights - 14 places for them so we have ₁₄C₇ ways to place them
place the greens - 7 places left, so we have ₇C₃ ways to place them
place the blues - only one way to place the 4 blues in the 4 places left

Ans: ₁₄C₇ x ₇C₃ = 3432x35 = 120,120 different strings of lights!