What is an alphabet?

  • It is a non-empty finite set of symbols.
  • Use ${\Sigma}$ to denote the alphabet.
  • Ex:
    1. $\Sigma$ = {0,1}
    2. $\Sigma$ = {a, b, c}
    3. $\Sigma$ = {a, b, c, … z}

What is a string?

  • It is a finite sequence of symbols from an alphabet.
  • Ex: $\Sigma$ = {a, b, c}
    1. w1 = “abc” - This is a string of 3 symbols.
    2. w2 = “acaba” - This is a string of 5 symbols.
  • There is a empty string w/ no symbols.
    • Represented by using the greek symbol lambda ($\lambda$)
    • So an empty string is represented as w1 = $\lambda$
  • At times, the term “word” is used to indicate a string,

What is concatenation?

  • Piecing multiple strings together.
  • Ex: if u = "abc" and u = "ababab", then uu = abcababab is made. uu is a concatenation.

What is reverse?

  • Order for last to first.
  • Ex: if w1 = "bbba", then rev(w1) = "abbb"

What is length (of a string)?

  • It is the total number of symbols in a given string.
  • Ex:
    1. w1 = "abbb", then len(w1) = 4
    2. w2 = "hello world!, then len(w2) = 12
    3. w3 = $\lambda$ then len(w3) = 0 since $\lambda$ represents an empty string.

What is a substring?

  • It is part of a string (it is continuous).
  • Ex: w1 = "abbababb"
    1. ab is a substring of w1
    2. baba is also a substring of w1
    3. baab is NOT a substring of w1

IMPORTANT: $\lambda$ will always be a substring whether the string is empty or not.

What is prefix and suffix?

  1. Prefix: start from the first position
  2. Suffix: start from the last position
  • Ex: w1 = "abbaab"
    1. Prefixes are: $\lambda$, a, ab, abb, abba, abbaa, abbaab
    2. Suffixes are: $\lambda$, b, ab, abb, abba, abbaa, abbaab

Main differences are in ‘a’ and ‘b’ characters right after $\lambda$

What is w^n notation?

  • If w is a string, the w^n denotes the string obtained by repeating w n times.
  • Ex: w1 = "abb" then:
    1. w1^3 = "abbabbabb"
    2. w1^0 = $\lambda$ since w^0 is an empty string (if n is 0, then it is an empty string since lambda is the only symbol/character that exists in the string).

Look at page 46 of Intro to Theory of Computation by Michael Sipser

What is $\Sigma$*-Notation (Star Closure of Alphabet $\Sigma$)

  • Given an alphabet set $\Sigma$, $\Sigma$* denotes all words that can be formed by using symbols $\Sigma$ including $\lambda$.

  • Ex1: $\Sigma$ = {0, 1}, then $\Sigma$* = All string that can be formed using 0 and 1, including $\lambda$

  • $\Sigma$+ - Notation: Includes everything but NOT lambda.

  • Ex2: Let $\Sigma$ = {a, b} be an alphabet and let $\Sigma$* be a language. How many words of length 3 does this language have?

    • It has 2^3 (or 8) words.

  • Ex3: S = {aa, b} and let S* be a language. How many words of length 4 are in S?

    • There are a total of 5 words of length 4 in S*.
      String Times
      “aaaa” x2a
      “bbbb” x4b
      “aabb” x1a, x2b
      “bbaa” x2b, x1a
      “baab” x1b, x1a, x1b

  • Ex4: How many words of length 5 in S* if S = {aa, b}?

    • There are a total of 8 words of length 5 in S*
      String Times
      “aabbb” x1a, x3b
      “bbbaa” x3b, x1a
      “aaaab” x2a, x1b
      “baaaa” x1b, x2a
      “baabb” x1b, x1a, x1b
      “bbaab” x2b, x1a, x1b
      “aabaa” x1a, x1b, x1a
      “bbbbb” x4b

Concatenation of Languages

  • if L1 and L2 are two languages, then L1 and L2 concatenated together is L1L2
    • L1L2 = {xy | x is in L1 and y is in L2}
  • Ex: L1 = {a, b, ab, abb} and L2 = {0, 1, 00}
    1. a00 is in L1L2
    2. abb1 is in L1L2
    3. 1a is NOT in L1L2 since 1 is NOT in L1
    4. a1 is in L1L2