Theoretical Computer Science

Tutorial Week 2

Munir Makhmutov

1 / 44
Agenda

Alphabets and Strings

Formal Languages
Operations

2 / 44
Alphabets and Strings

Definition
An alphabet is a finite set of symbols

Examples

{0, 1}

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

{a, b, c, d, . . . , x, y , z}

3 / 44
Alphabets and Strings

Definition
A string over an alphabet Σ is a finite sequence of symbols in Σ

Examples
For Σ = {0, 1},
010011
11100011

4 / 44
Alphabets and Strings

Definition
A string over an alphabet Σ is a finite sequence of symbols in Σ

Examples
For Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9},

123456

666
2023

5 / 44
Alphabets and Strings

Definition
A string over an alphabet Σ is a finite sequence of symbols in Σ

Examples
For Σ = {a, b, c, d, . . . , x, y , z},

peace

war
dfklgnkjrbgjrbg

6 / 44
Alphabets and Strings

Definition
The length of a string s is the number of symbols of s
and denoted as |s|

Examples

|peace| = 5
|war | = 3
|dfklgnkjrbgjrbg | = 15

7 / 44
Alphabets and Strings

Definition
ϵ is the null string (empty string) over any alphabet.

Property

|ϵ| = 0

8 / 44
Alphabets and Strings

Definition
For two strings x and y , the concatenation x · y is the operation of
joining “end-to-end”.

Examples
For x =“123” and y =“987”,

x · y = “123987”

9 / 44
Alphabets and Strings

Definition
For two strings x and y , the concatenation x · y is the operation of
joining “end-to-end”.

Examples
For x = “back” and y = “end”,

x · y = “backend”

y · x = “endback”

10 / 44
Alphabets and Strings

Definition
For two strings x and y , the concatenation x · y is the operation of
joining “end-to-end”.

Examples
For x = “back” and y = “end”,

x · y = “backend”

y · x = “endback”
Non-commutative!

10 / 44
Alphabets and Strings

Property

(x · y ) · z = x · (y · z)

Examples
For x = “ab”, y = “cd” and z = “ef ”,

(x · y ) · z = “abcd” · “ef ” = “abcdef ”

x · (y · z) = “ab” · “cdef ” = “abcdef ”

11 / 44
Alphabets and Strings

Property

(x · y ) · z = x · (y · z)

Examples
For x = “ab”, y = “cd” and z = “ef ”,

(x · y ) · z = “abcd” · “ef ” = “abcdef ”

x · (y · z) = “ab” · “cdef ” = “abcdef ”
Associative!

11 / 44
Alphabets and Strings

Property with null

∀x (x · ϵ = ϵ · x = x)

ϵ is an identity element

12 / 44
Agenda

Alphabets and Strings

Formal Languages
Operations

13 / 44
Formal Languages

Definition
The set of all strings over Σ is denoted by Σ∗

Examples
For Σ = {0, 1},

Σ∗ = {ϵ, 0, 1, 00, 01, 10, 11, 000, 001, 010, . . .}

14 / 44
Formal Languages

Definition
A language L is a set of strings over an alphabet Σ.

Equivalent definition

L ⊆ Σ∗

15 / 44
The Naive Set Theory

Definition of a set
A = {x ∈ U | P(x)}

A = {a1 , a2 , . . . , an }

Example

{x ∈ Z | x < 0}
U is a universal set
Z is a set of all integers

16 / 44
Formal Languages

Alphabet
For Σ = {0, 1},

Σ∗ = {ϵ, 0, 1, 00, 01, 10, 11, 000, 001, 010, . . .}

Languages

L1 = {00000000, 00000001, . . . , 11111110, 11111111} =

= {x ∈ {0, 1}∗ | |x| = 8}
L2 = {0, 00, 01, 000, 001, 010, . . .} = {0x | x ∈ Σ∗ }

17 / 44
Formal Languages

Alphabet
For Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9},

Σ∗ = N ∪ {ϵ}

Languages

L1 = {0, 2, 4, 6, 8, 10, . . .} = {x ∈ Σ∗ | x is even }

L2 = {2, 3, 5, 7, 13, . . .} = {x ∈ Σ∗ | x is prime }

18 / 44
Formal Languages

Alphabet
For Σ = {a, b, c, d, . . . , x, y , z}

Languages

Russian, English, Italian, Tatar,. . .

19 / 44
Formal Languages

Alphabet
For Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, −, =}

Arithmetic

{0 + 0 = 0, 0 − 0 = 0, . . . , 12 + 32 = 44, . . . , 52 − 39 = 13, . . .}

20 / 44
Agenda

Alphabets and Strings

Formal Languages
Operations
Operations from Set Theory
Special operations

21 / 44
1. Complement

Complement of a set

Ac = A = {x ∈ U | x ∈
/ A}

Example
If U = {1, 2, 3, 4} and A = {1, 3}, then

A = {2, 4}

22 / 44
Complement

Complement of a language
For an alphabet Σ,

Lc = L = {x ∈ Σ∗ | x ∈
/ L}

Example
For Σ = {0, 1}, if L = {0x | x ∈ Σ∗ }, then

L=

23 / 44
Complement

Complement of a language
For an alphabet Σ,

Lc = L = {x ∈ Σ∗ | x ∈
/ L}

Example
For Σ = {0, 1}, if L = {0x | x ∈ Σ∗ }, then

L = {1x | x ∈ Σ∗ } ∪ {ϵ}

23 / 44
Union

Union
A ∪ B = {x ∈ U | x ∈ A ∨ x ∈ B}

Example
If A = {1, 2, 3} and B = {2, 3, 4}, then

A ∪ B = {1, 2, 3, 4}

24 / 44
Intersection

Intersection
A ∩ B = {x ∈ U | x ∈ A ∧ x ∈ B}

Example
If A = {1, 2, 3} and B = {2, 3, 4}, then

A ∩ B = {2, 3}

25 / 44
Difference

Difference
A \ B = {x ∈ U | x ∈ A ∧ x ∈
/ B}

Example
If A = {1, 2, 3} and B = {2, 3, 4}, then

A \ B = {1}

26 / 44
Formal Languages

2. Union
L1 ∪ L2 = {s ∈ Σ∗ | s ∈ L1 ∨ L2 }

3. Intersection
L1 ∩ L2 = {s ∈ Σ∗ | s ∈ L1 ∧ s ∈ L2 }

4. Difference
L1 \ L2 = {s ∈ Σ∗ | s ∈ L1 ∧ s ∈
/ L2 }

27 / 44
The Naive Set Theory

Definition
X × Y = {(x, y ) | x ∈ X ∧ y ∈ Y }

Example
If A = {1, 2, 3} and B = {a, b}, then

A × B = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)}

28 / 44
The Naive Set Theory

Definition
X1 × · · · × Xn = {(x1 , . . . , xn ) | x1 ∈ X1 ∧ . . . ∧ xn ∈ Xn }

Example
· · × X} = X n
| × ·{z
X
n times

29 / 44
The Naive Set Theory

Definition
For a set A, the power of A is the set

2A = P(A) = {B | B ⊆ A}

Examples
1) If A = {a} then P(A) = {∅, {a}}
2) If A = {a, b} then P(A) = {∅, {a}, {b}, {a, b}}

30 / 44
The Naive Set Theory

Definition
Intuitively, the cardinality of a set A, denoted by |A|, is the number
of elements of A.

Examples
1. |∅| = 0
2. if A = {2} then |A| = 1
3. if A = {1, 2, 3} then |A| = 3

31 / 44
Relationship

Question 1
What is the difference between sets and strings?

Question 2
What is the difference between ∅ and ϵ?

Question 3
What is the difference between the cardinality and the length?

32 / 44
Agenda

Alphabets and Strings

Formal Languages
Operations
Operations from Set Theory
Special operations

33 / 44
Formal Languages

Concatenation
L1 · L2 = {x · y | x ∈ L1 ∧ y ∈ L2 }

Example
If L1 = {1, 2, 3} and L2 = {a, b}, then

L1 · L2 = {1a, 1b, 2a, 2b, 3a, 3b}

34 / 44
Formal Languages

Concatenation
L1 · L2 = {x · y | x ∈ L1 ∧ y ∈ L2 }

Example
If L1 = {1, 12} and L2 = {ϵ, 2}, then

L1 · L2 = {1, 12, 122}

35 / 44
Formal Languages

Concatenation
L1 · L2 = {x · y | x ∈ L1 ∧ y ∈ L2 }

Example
If L1 = {ϵ, a} and L2 = {ϵ, a, aa, aaa, . . .}, then

L1 · L2 =

36 / 44
Formal Languages

Concatenation
L1 · L2 = {x · y | x ∈ L1 ∧ y ∈ L2 }

Example
If L1 = {ϵ, a} and L2 = {ϵ, a, aa, aaa, . . .}, then

L1 · L2 = L2

L1 × L2 ̸= L2 for any nonempty L1 , L2

36 / 44
Formal Languages

Kleene star
L∗ = {x1 x2 . . . xn | n ∈ N, x1 , x2 , . . . xn ∈ L}

Example
For Σ = {a, b}, if L = {a} then

L∗ = {ϵ, a, aa, aaa, . . .}

37 / 44
Formal Languages

Kleene star
L∗ = {x1 x2 . . . xn | n ∈ N, x1 , x2 , . . . xn ∈ L}

Example
For Σ = {a, b}, if L = {ab} then

L∗ = {ϵ, ab, abab, ababab, . . .}

38 / 44
Formal Languages

Kleene star
Let Σ be an alphabet. Kleene star of Σ contains all strings and
denotes Σ∗ (as before).

Special case
Σ+ = Σ∗ \ {ϵ} - Kleene plus

39 / 44
Formal Languages

Special cases

Lk = {x1 x2 . . . xk | x1 , x2 , . . . xk ∈ L}

Example
For Σ = {a, b}, if L = {a} then

Lk = {aa . . . a}}
| {z
k times

40 / 44
Formal Languages

Special cases

Lk = {x1 x2 . . . xk | x1 , x2 , . . . xk ∈ L}

Example
For Σ = {a, b},

Σ2 =

41 / 44
Formal Languages

Special cases

Lk = {x1 x2 . . . xk | x1 , x2 , . . . xk ∈ L}

Example
For Σ = {a, b},

Σ2 = {aa, ab, ba, bb}

41 / 44
Formal Languages

Special cases

ak = aa . . . a}
| {z
k times

Example
For Σ = {a, b},

Σ3 =

42 / 44
Formal Languages

Special cases

ak = aa . . . a}
| {z
k times

Example
For Σ = {a, b},

Σ3 = {a3 , a2 b, aba, ab 2 , ba2 , bab, b 2 a, b 3 }

42 / 44
Formal Languages

Special cases

ak = aa . . . a}
| {z
k times

Example
For Σ = {a, b},

Σ3 = {a3 , a2 b, aba, ab 2 , ba2 , bab, b 2 a, b 3 }

OR

Σ3 = {aaa, aab, aba, abb, baa, bab, bba, bbb}

42 / 44
Summary

Alphabets and Strings

Formal Languages
Operations
Operations from Set Theory
Special operations

43 / 44
Thank you for your attention!

44 / 44