Lab Session #1 #

Introductory notes #

Welcome to our laboratory exercises! Each week, you’ll have the opportunity to work on hands-on projects and experiments that will help you better understand the material covered in class.

Important information

To make sure you’re getting the most out of the lab sessions, we’ll be assessing your performance in a few different ways and the final grade will be calculated as follows:

• Mid-term Exam (20%)
• Final Exam (30%)
• 2 Assignments (30%)
• 6 Quizzes (25%)

We understand that sometimes you may want to switch lab groups to work with different classmates. That’s why we allow group switching under the following conditions:

• The group size limit is 30 students. You’ll need to get approval from the TA.

We’re excited for you to dive into the lab sessions and gain a deeper understanding of the material. If you have any questions or concerns, please don’t hesitate to reach out to the TA or instructor.

Policy and Procedures on Cheating and Plagiarism

Tests and Exams policy: If two or more students are caught communicating for any reason during exams (including mid-terms) they will be asked to leave the room and their exam will be failed. Same will happen for unauthorized use of devices.

Report policy

If a submitted report contains work other than student’s one it is necessary to explicitly acknowledge the source. It is encouraged to refer and quote other works, but it has to be made clear which words and ideas are property and creation of the student, and which ones have come from others (which must not correspond to more than 30% of the work). If two or more reports show evidence of being produced by unauthorized cooperative work, i.e. copied from fellow students, they will be all failed without further investigation on who produced the results and who actually copied.

Agenda #

• Introduction to sets and set notation
• Overview of formal languages and their properties
• Operations on formal languages, including union, intersection, and complement
• Discussion of some common types of formal languages, such as regular languages and context-free languages
• Examples and exercises to reinforce understanding of the material.

Introduction to sets and set notation #

A set is a collection of distinct objects, called elements or members of the set. Sets are usually denoted by enclosing their elements in curly braces {}. For example, the set of natural numbers less than 5 can be written as {1, 2, 3, 4}. Sets can also be defined using set-builder notation, where a rule or property that the elements must satisfy is given. For example, the set of all even natural numbers can be written as {x | x is an even natural number}. Sets can also be represented using Venn diagrams, which are diagrams that show all possible logical relations between a finite collection of sets.

Finite set #

A finite set is a set that has a finite number of elements. For example, the set of integers from 1 to 10 is a finite set because it has 10 elements. In contrast, the set of all integers is an infinite set because it has an infinite number of elements.

A finite set can be described, at least in principle, by listing its elements: $A = \{1, 2, 4, 8\}$ says that $A$ is the set whose elements are $1, 2, 4, 8.$

Infinite set #

For infinite (even for finite sets if they have more than just a few elements) sets ellipses $(\dots)$ are sometimes used to describe how the elements might be listed. An ellipsis is a set of three periods $(\dots)$ indicating an omission: $B = \{0, 3, 6, 9, \ldots\}$

A more reliable way is to give the property that characterises their elements (also called set comprehension). Set $B = \{0, 3, 6, 9, \ldots\}$ can be described as: $B = \{x \mid x \text{ is a non-negative integer multiple of 3}\}$ It reads: $B$ is the set of all $x$ such that $x$ is a non-negative integer multiple of $3.$

Notation #

• For any set $A$ the statement that $x$ is an element of $A$ is written: $x \in A$ .
• $A \subseteq B$ means that $A$ is a subset of $B$ : every element of $A$ is an element of $B$ .
• $\emptyset$ denotes the empty set: the set with no elements.

To show that two sets $A$ and $B$ are the same, we must show that $A$ and $B$ have exactly the same elements, i.e. $A \subseteq B$ and $B \subseteq A$ .

Operations #

For two sets $A$ and $B$ , we can define their union $A \cup B$ , their intersection $A \cap B$ , and their difference $A \backslash B$ (sometimes denoted as $A - B$ ), as follows $(\vee, \wedge$ denote the logical ‘or’ and logical ‘and’ respectively).

• $A \cup B = \{x \mid x \in A \vee x \in B\}$
• $A \cap B = \{x \mid x \in A \wedge x \in B\}$
• $A \backslash B = \{x \mid x \in A \wedge x \not \in B\}$

Below, is a python code that shows simple operations on sets:

# Define two sets
A = {1, 2, 3, 4, 5}
B = {4, 5, 6, 7, 8}

# Use the union operator to combine the sets
print("A union B:", A | B)

# Use the intersection operator to find common elements
print("A intersection B:", A & B)

# Use the difference operator to find elements in A that are not in B
print("A - B:", A - B)

# Use the symmetric difference operator to find elements
# that are in either A or B but not both
print("A symmetric difference B:", A ^ B)

# Check if A is a subset of B
print("Is A a subset of B:", A.issubset(B))

# Check if A is a proper subset of B
print("Is A a proper subset of B:", A.issubset(B) and A != B)

# Check if A is a superset of B
print("Is A a superset of B:", A.issuperset(B))

Union of any number of sets #

If $A_0, A_1, A_2, \ldots$ are sets, the union of these sets can be denoted as $\bigcup \{A_i \mid i \ge 0\} = \{x \mid x \in A_i \text{ for at least one $i$ with }i \ge 0\}$

Power Sets #

For a set $A$ , the set of all subsets of $A$ is called the power set. Can be denoted as $\mathcal{P}(A)$ or as $2^{A}$

• Power set of set $\{a, b, c\}$ is $\{\emptyset, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}\}$

For a set $A$ , the set $\mathcal{P}(A)$ has exactly $2^{n}$ elements, where $n$ is the cardinality of $A$ (the cardinality of a set is a measure of a set’s size, meaning the number of elements in the set).

Overview of formal languages and their properties #

A formal language is a set of strings (sequences of symbols) that are defined by a set of rules or grammar. These rules specify how the symbols can be combined to form valid strings in the language. Formal languages are used in many fields, such as mathematics, computer science, and linguistics, to precisely define and manipulate abstract concepts. Examples of formal languages include programming languages, mathematical notation, and formal logic.

Notation and Terminology #

Alphabet: a finite set of symbols, e.g. $\{a, b\}$ , or $\{0, 1\}$ . Normally denoted by $\Sigma$
String: a string over an alphabet ( $\Sigma$ ) is a finite sequence of symbols in $\Sigma$ .
Length: for a string $x$ , $\left\vert{x}\right\vert$ is the number of symbols of $x$ .
Empty string: is the null string over $\Sigma$ . It is denoted as $\epsilon$ . By definition, $\left\vert{\epsilon}\right\vert = 0$
Set of all strings: the set of all strings over $\Sigma$ is denoted by $\Sigma^*$ , e.g. for the alphabet $A = \{a, b\}$ \ $A^* = \{\epsilon, a, b, aa, ab, ba, bb, aaa, aab, \ldots\}$

Concatenation of strings #

If $x$ and $y$ are two strings over an alphabet, the concatenation $xy$ (sometimes denoted as $x\cdot y$ ) consists of the symbols of $x$ followed by those of $y$ :

$x = ab$ $y = bab$ $xy = abbab$

Concatenation is an associative operation: $(xy)z = x(yz)$ for all possible strings $x$ , $y$ , and $z$ .

Constructing new Languages #

Languages are sets!

• Operations on languages are ways of constructing new languages: for two languages $L_1$ and $L_2$ over the alphabet $\Sigma$ , $L_1 \cup L_2$ , $L_1 \cap L_2$ , and $L_1 \backslash L_2$ are also languages over $\Sigma$ .
• String operation of concatenation is also used to construct new languages: if $L_1$ and $L_2$ are both languages over $\Sigma$ , the concatenation of $L_1$ and $L_2$ is the language

Example: $\{a, aa\}\{\epsilon, b, ab\} = \{a, ab, aab, aa, aab, aaab\}$

Is this statement true? $L_1L_2 = L_2L_1$

Exponential notation #

The concatenation of $k$ copies of a single symbol $a$ , a single string $s$ , or a single language $L$ is defined as:
If $k$ = $0,$ then $a^k = \{\epsilon\}$

If $k$ > $0,$ then $a^k = aa \ldots a$ where there are $k$ occurrences of $a$ , similarly for $s^k$ and $L^k$ . In the case where $L$ is simply the alphabet $\Sigma,$ $\Sigma^k = \{x \in \Sigma^* \mid \left\vert{x}\right\vert = k \}$

Example: $\Sigma = \{0, 1\} \\ \Sigma^2 = \{00, 01, 10, 11\}$

Operations on Languages #

• Union
• Intersection
• Set difference
• Complement: if $L$ is a language over $\Sigma,$ $\overline{L}=\Sigma^* \backslash L$ The complement consists of all strings not in the language!
• Concatenation: $L_1L_2 = \{xy \mid x \in L_1, y \in L_2\}$
• Power of n $L^n = \{x_1x_2...x_n \mid x_i \in L \text{ for all } 1 \leq i \leq n\}$
• Kleen Star $L^* = \{x_1x_2...x_n \mid n \in \mathbb{N}, x_1,x_2,...,x_n \in L\} = \bigcup\limits_{n \in \mathbb{N}} L^n$

Exercises on sets and sets notation #

Exercises (0) #

1. What are the sets $D$ and $E$ ?

• $D = \{\{x\} \mid x \text{ is a non-negative integer such that } x \leq 4 \}$
• $E = \{3i + 5j \mid i \text{ and } j \text{ are non-negative integers}\}$

2. Are the following statements true?

• $\{0, 1\} = \{1, 0\}$
• $\{0, 1, 2, 1, 0\} = \{1, 1, 1, 1, 0, 2, 2\}$

Exercises (1) #

Construct the power set for the following sets:

• $\{a, b\}$
  Solution ▾

  The power set of the set $\{a,b\}$ is $\{\{\}, \{a\}, \{b\}, \{a,b\}\}$
• $\{0, 1\} \cup \{1, 2\}$
  Solution ▾

  The power set of the set $\{0,1\} \cup \{1,2\}$ is: $\{\{\}, \{0\}, \{1\}, \{2\}, \{0,1\}, \{0,2\}, \{1,2\}, \{0,1,2\}\}$
• $\{z\}$
  Solution ▾

  The power set of the set $\{z\}$ is: $\{\{\},\{z\}\}$
• $\{0, 1, 2, 3, 4\} \cap \{1, 3, 5, a\}$
  Solution ▾

  The power set of the set $\{0, 1, 2, 3, 4\} \cap \{1, 3, 5, a\}$ is: $\{\{\},\{1\},\{3\}, \{1,3\}\}$
• $\{0, 1, 2, 3\} \backslash \{1, 3, 5, a\}$
  Solution ▾

  The power set of the set $\{0, 1, 2, 3, 4\} \backslash \{1, 3, 5, a\}$ is: $\{\{\},\{0\},\{2\}, \{0,2\}\}$
• $\emptyset$
  Solution ▾

  The power set of the set $\emptyset$ is: $\{\emptyset\}$

Determine the following languages over the alphabet $\Sigma = {0, 1}$

• $\Sigma^0$

  Solution ▾

  $\Sigma^0 = \{\epsilon\}$

• $\Sigma^4$

  Solution ▾

  $\Sigma^4 = \{0000, 0001, 0010, 0011,\\ 0100, 0101, 0110, 0111,\\ 1000, 1001, 1010, 1011,\\ 1100, 1101, 1110, 1111\}$ The set $\Sigma^4$ is the set of all 16 possible combinations: $2^{A}$

• $\mathcal{P}(\Sigma)$

  Solution ▾

  $\mathcal{P}(\Sigma) = \{\emptyset, \{0\}, \{1\}, \{0, 1\}\}$

• $\mathcal{P}(\Sigma^*)$

  Solution ▾

  $\mathcal{P}(\Sigma^*) =$ (Infinite set which includes empty set and all combinations of 0s and 1s)

Exercises (2) #

Find a possible alphabet for the following languages

• The language $L = \{oh, ouch, ugh\}$

  Solution ▾

  The language $L = \{oh, ouch, ugh\}$ : $\Sigma = \{o, h, u, c, g\}$

• The language $L = \{apple, pear, 4711\}$

  Solution ▾

  The language $L = \{apple, pear, 4711\}$ : $\Sigma = \{a, p, l, e, r, 4, 7, 1\}$

• The language of all binary strings

  Solution ▾

  $\Sigma = \{0, 1\}$

Determine what the Kleene star operation produces over the following alphabets:

• $\Sigma = \{0, 1\}$

  Solution ▾

  $\Sigma^* = \{0, 1\}$ : All binary strings

• $\Sigma = \{a\}$

  Solution ▾

  $\Sigma = \{a\}$ : All strings which contain nothing but $a's$

• $\Sigma = \emptyset\$ (the empty alphabet)

  Solution ▾

  $\Sigma = \{\emptyset\}$ (the empty alphabet): the language that contains only the empty string

Exercises (3) #

State the alphabet $\Sigma$ for the following languages:

• $L = \Sigma^* = \{\epsilon, 0, 1, 00, 01, 10, 11, 000, \ldots\}$

  Solution ▾

  $L = \Sigma^* = \{\epsilon, 0, 1, 00, 01, 10, 11, 000, \ldots\}: \Sigma = \{0, 1\}$

• $L = \Sigma^* = \{\epsilon, a, aa, aaa, aaaa, \ldots\}$

  Solution ▾

  $L = \Sigma^* = \{\epsilon, a, aa, aaa, aaaa, \ldots\}: \Sigma = \{a\}$

Assuming that $\Sigma =\{0, 1\}$ , construct complement languages for the following:

• $\overline{\{010, 101, 11\}}$

  Solution ▾

  $L = \{\epsilon, 0, 1, 00, 01, 10, 000, 001, 011, 100, 110, 111, 0000, 0001, \ldots\}$

• $\overline{\Sigma^* \backslash \{110\}}$

  Solution ▾

  $L = \{110\}$

State the following languages explicitly

• $\mathcal{P}(\{a, b\}) \backslash \mathcal{P}(\{a, c\})$

  Solution ▾

  The expression represents the set difference between two power sets: $L = \{\{b\}, \{a, b\}\}$

• $\{x \mid x,y \in \mathbb{N} \wedge \exists y : y < 10 \wedge (y + 2 = x)\}$ ( $\mathbb{N}$ is the set of all non-negative integers)

  Solution ▾

  This mathematical expression states that "there is a set x such that x and y are elements of the set of non-negative integers and there exists a y such that y is less than 10 and y + 2 = x." In other words, x is any non-negative integer that can be obtained by adding 2 to a non-negative integer less than 10. $L = \{2, 3, 4, 5, 6, 7, 8, 9, 10, 11\}$

Exercises on operations on languages #

Exercises (4) #

• Let $L=\{a^i, i \geq 0 \}$ be a language over $\Sigma=\{a, b\}$ . Find $\overline{L}$ and $L^*$

  Solution ▾

  Let $L=\{a^i, i \geq 0 \}$ , $\Sigma=\{a, b\}$ . $\\$ The complement language: $\overline{L}=$ all nonempty strings containing at least one b; $\\$ The Kleen star operation: $L^*=\{a^i, i \geq 0 \}$ $\\$ $L^* = \{\epsilon, a, aa, aaa, aaaa, ...\}$

• Let $L_1$ , $L_2$ be languages over $\Sigma=\{a, b\}$ . Find $L_1L_2$

  • $L_1=\{\epsilon,a,aa\}$ , $L_2=\{aa,aaa\}$

    Solution ▾

    $\{\epsilon,a,aa\}\{aa,aaa\}=\{aa,aaa,aaaa,aaaaa\}$ . $\\$

  • $L_1=\{a,a^2, a^4\}$ , $L_2=\{b^0, b^2, b^3\}$

    Solution ▾

    $\{a,a^2, a^4\}\{b^0, b^2, b^3\}=\{a,aa, aaaa\}\{\epsilon, bb, bbb\}=$ $\\$ $\{a,aa,aaaa,abb,aabb,aaaabb,abbb,aabbb,aaaabbb\}$

• Let $L=\{0,01,001\}$ . Find $L^2$ .

  Solution ▾

  $\{0,01,001\}^2=\{00,001,0001,010,0101,01001,0010,00101,001001\}$ $\\$

• Describe in plain English the following languages over $\Sigma=\{a, b\}$ :

  • $L = \{a, b\}^*$

    Solution ▾

    $L = \{a, b\}^*$ - all strings of a's and b's, including empty string $\\$

  • $L = \{a\}^* \cup \{b\}^*$

    Solution ▾

    $L = \{a\}^* \cup \{b\}^*$ - empty string and strings of only a's or only b's $\\$

  • $L = \{a\}^* \cap \{b\}^*$

    Solution ▾

    $L = \{a\}^* \cap \{b\}^*$ - empty string $\\$

  • $L = \{aa\}^* \backslash \{aaaa\}^*$

    Solution ▾

    $L = \{aa\}^* \backslash \{aaaa\}^*$ - strings of even number of a's which is not a multiple of 4 $\\$

• Write out in full the strings $0^5, 0^31^3, (010)^2, (01)^30, 1^0$

  Solution ▾

  $00000, 000111, 010010, 0101010, \epsilon$ $\\$

Exercises (5) #

Perform operations on the languages over $\Sigma=\{0, 1\}$ :

• $L_1 = \{0,1,00,11,000,111,...\},$

• $L_2 = \{0,1\}^*,$

• $L_3=\{w \mid w \in \Sigma^*, |w|=1\},$

• $L_4=\{w \mid w \in \Sigma^*, |w|=2\},$

• $L_5=\{w \mid w \in \Sigma^*, |w| \geq 1\}$

1. $L_1 \cup L_2, \quad L_3 \cup L_4$

   Solution ▾

   $L_1 \cup L_2 = L_2$ $\\$ $L_3 \cup L_4 = \{0,1,00,11,01,10\}$

2. $L_1 \cap L_2, \quad L_1 \cap L_3, \quad L_1 \cap L_4, \quad L_1 \cap L_5, \quad L_3 \cap L_4$

   Solution ▾

   $L_1 \cap L_2 = L_1$ $\\$ $L_1 \cap L_3 = L_3$ $\\$ $L_1 \cap L_4 = \{00,11\}$ $\\$ $L_1 \cap L_5 = L_1$ $\\$ $L_3 \cap L_4 = \emptyset$ $\\$

3. $L_1 \backslash L_2, \quad L_1 \backslash L_3, \quad L_3 \backslash L_4,\quad L_4 \backslash L_5, \quad L_5 \backslash L_4$

   Solution ▾

   $L_1 \backslash L_2 =\emptyset$ $\\$ $L_1 \backslash L_3 =\{00,11,000,111,...\}$ $\\$ $L_3 \backslash L_4 = L_3 = \{0,1\}$ $\\$ $L_4 \backslash L_5 = \emptyset$ $\\$ $L_5 \backslash L_4 = \{w \mid w \in \Sigma^*, |w| = 1 \text{ or } |w| \geq 3\}$ $\\$

4. $\overline{L_1}, \quad \overline{L_2}, \quad \overline{L_3}, \quad \overline{L_5 \backslash L_4}$

   Solution ▾

   $\overline{L_1} = \{\epsilon, 01, 10, 010, 011, 100, 101, ...\}$ $\\$ $\overline{L_2} = \emptyset$ $\\$ $\overline{L_3} = \{\epsilon, 00,11,01,10,000,111,010,011,100,101,..\}$ $\\$ $\overline{L_5 \backslash L_4} = L_4 \cup \{\epsilon\}$ $\\$

5. $L_1L_2, \quad L_3L_4, \quad L_4L_3$

   Solution ▾

   $L_1L_2 = L_2\backslash \{\epsilon\}$ $\\$ $L_3L_4 =\{000,011,001,010,100,111,101,110\}$ $\\$ $L_4L_3 = L_3L_4 =\{000,001,110,111,010,011,100,101\}$ $\\$

6. $L_2^*, \quad L_3^*, \quad L_4^*$

   Solution ▾

   $L_2^* = L_2$ $\\$ $L_3^* = L_2$ $\\$ $L_4^* = \{w \mid w \in \Sigma^*, |w|=2k, k \in \mathbb{N} \}$ $\\$