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.

More ▾

Sets: In mathematics, a set is a collection of distinct objects, considered as an object in its own right. Sets are one of the most fundamental concepts in mathematics, and can be used to model nearly everything in the mathematical universe.

Formal Languages: A formal language is a set of finite sequences of symbols, also known as strings, that are generated by a formal grammar. Formal languages are used in mathematical logic, computer science, and the study of programming languages.

Operations on Formal Languages: There are several operations that can be performed on formal languages, such as union, intersection, complement, and concatenation. Union combines two languages into one, intersection finds the common strings between two languages, complement finds the strings that are in one language but not in another, and concatenation combines two languages by appending the strings of one language to the end of the strings of another.

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))

More ▾

Symmetric difference between two sets - The set which contains the elements which are either in set A or in set B but not in both is called the symmetric difference between two given sets.
A proper subset of a set A is a subset of A that is not equal to A.
A set A is a superset of another set B if all elements of the set B are elements of the set A

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\}\]

\[\bigcup_{i = 0}^\infty A_i\]

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

\[L_1L_2 = \{xy \mid x \in L_1, y \in L_2\}\]

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\} %L_1L_2 = \{xy \mid x \in L_1 \wedge L_2\}\]
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 %L_1L_2 = \{xy \mid x \in L_1 \wedge L_2\}\]

Exercises on sets and sets notation #

Exercises (0) #

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}\}$

Solution #1 ▾

The set \(D\) is a set, where each set in \(D\) is a singleton set containing a non-negative integer that is less than or equal to \(4\) . A singleton set is a set that contains exactly one element. So, the set \(D\) is defined as follows: \(D = \{\{0\}, \{1\}, \{2\}, \{3\}, \{4\}\}\) Because the set \(D\) is a set of singletons and every singleton set of a non-negative integer such that \(x \leq 4\) will be included in this set. renderMathInElement(document.getElementsByClassName("katex-inner"))

Solution #2 ▾

This set is infinite and all numbers can be expressed in the form \(3i + 5j,\) for some non-negative integers \(i\) and \(j\) . Thus, \(E = \{..., 3i + 5j, ...\}\) renderMathInElement(document.getElementsByClassName("katex-inner"))

Are the following statements true?

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

Solution #1 ▾

Yes, the statement is true. In set theory, two sets are considered equal if and only if they have the same elements, regardless of the order of the elements or the number of times they appear. The set \(\{0, 1\}\) contains the elements \(0\) and \(1\) in that order, while the set \(\{1, 0\}\) contains the same elements but in a different order. renderMathInElement(document.getElementsByClassName("katex-inner"))

Solution #2 ▾

Yes, the statement is true. In set theory, two sets are considered equal if and only if they have the same elements, regardless of the order of the elements. The set \(\{0, 1, 2, 1, 0\}\) contains the elements \(0, 1, 2\) and each element appears more than one time. The set \(\{1, 1, 1, 1, 0, 2, 2\}\) also contains the same elements but in different order and also multiple times. However, the sets \(\{0, 1, 2, 1, 0\}\) and \(\{1, 1, 1, 1, 0, 2, 2\}\) are made with the same alphabet as both sets contain only integers from \(0\) to \(2\) as elements. renderMathInElement(document.getElementsByClassName("katex-inner"))

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\}\}$ renderMathInElement(document.getElementsByClassName("katex-inner"))$
$\{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\}\}$ renderMathInElement(document.getElementsByClassName("katex-inner"))$
$\{z\}$
Solution ▾
$The power set of the set $\{z\}$ is: $\{\{\},\{z\}\}$ renderMathInElement(document.getElementsByClassName("katex-inner"))$
$\{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\}\}$ renderMathInElement(document.getElementsByClassName("katex-inner"))$
$\{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\}\}$ renderMathInElement(document.getElementsByClassName("katex-inner"))$
$\emptyset$
Solution ▾
$The power set of the set $\emptyset$ is: $\{\emptyset\}$ renderMathInElement(document.getElementsByClassName("katex-inner"))$

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

$\Sigma^0$
Solution ▾
$$\Sigma^0 = \{\epsilon\}$ renderMathInElement(document.getElementsByClassName("katex-inner"))$
$\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}$ renderMathInElement(document.getElementsByClassName("katex-inner"))$
$\mathcal{P}(\Sigma)$
Solution ▾
$\[\mathcal{P}(\Sigma) = \{\emptyset, \{0\}, \{1\}, \{0, 1\}\}\] renderMathInElement(document.getElementsByClassName("katex-inner"))$
$\mathcal{P}(\Sigma^*)$
Solution ▾
$$ \mathcal{P}(\Sigma^*) = $ (Infinite set which includes empty set and all combinations of 0s and 1s) renderMathInElement(document.getElementsByClassName("katex-inner"))$

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\}$ renderMathInElement(document.getElementsByClassName("katex-inner"))$
The language $L = \{apple, pear, 4711\}$
Solution ▾
$The language $L = \{apple, pear, 4711\}$ : $\Sigma = \{a, p, l, e, r, 4, 7, 1\}$ renderMathInElement(document.getElementsByClassName("katex-inner"))$
The language of all binary strings
Solution ▾
$$\Sigma = \{0, 1\}$ renderMathInElement(document.getElementsByClassName("katex-inner"))$

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

$\Sigma = \{0, 1\}$
Solution ▾
$$\Sigma^* = \{0, 1\}$ : All binary strings renderMathInElement(document.getElementsByClassName("katex-inner"))$
$\Sigma = \{a\}$
Solution ▾
$$\Sigma = \{a\}$ : All strings which contain nothing but $a's$ renderMathInElement(document.getElementsByClassName("katex-inner"))$
$\Sigma = \emptyset\ $ (the empty alphabet)
Solution ▾
$$\Sigma = \{\emptyset\}$ (the empty alphabet): the language that contains only the empty string renderMathInElement(document.getElementsByClassName("katex-inner"))$

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\}$ renderMathInElement(document.getElementsByClassName("katex-inner"))$
$L = \Sigma^* = \{\epsilon, a, aa, aaa, aaaa, \ldots\}$
Solution ▾
$$L = \Sigma^* = \{\epsilon, a, aa, aaa, aaaa, \ldots\}: \Sigma = \{a\}$ renderMathInElement(document.getElementsByClassName("katex-inner"))$

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\}\] renderMathInElement(document.getElementsByClassName("katex-inner"))$
$\overline{\Sigma^* \backslash \{110\}}$
Solution ▾
$\[ L = \{110\} \] renderMathInElement(document.getElementsByClassName("katex-inner"))$

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\}\} \] renderMathInElement(document.getElementsByClassName("katex-inner"))$
$\{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\} \] renderMathInElement(document.getElementsByClassName("katex-inner"))$

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, ...\}$ renderMathInElement(document.getElementsByClassName("katex-inner"))$
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\}$ . $\\$ renderMathInElement(document.getElementsByClassName("katex-inner"))$
- $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\}$ renderMathInElement(document.getElementsByClassName("katex-inner"))$
Let $L=\{0,01,001\}$ . Find $L^2$ .
Solution ▾
$$\{0,01,001\}^2=\{00,001,0001,010,0101,01001,0010,00101,001001\}$ $\\$ renderMathInElement(document.getElementsByClassName("katex-inner"))$
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 $\\$ renderMathInElement(document.getElementsByClassName("katex-inner"))$
- $L = \{a\}^* \cup \{b\}^*$
  Solution ▾
  $$L = \{a\}^* \cup \{b\}^*$ - empty string and strings of only a's or only b's $\\$ renderMathInElement(document.getElementsByClassName("katex-inner"))$
- $L = \{a\}^* \cap \{b\}^*$
  Solution ▾
  $$L = \{a\}^* \cap \{b\}^*$ - empty string $\\$ renderMathInElement(document.getElementsByClassName("katex-inner"))$
- $L = \{aa\}^* \backslash \{aaaa\}^*$
  Solution ▾
  $$L = \{aa\}^* \backslash \{aaaa\}^*$ - strings of even number of a's which is not a multiple of 4 $\\$ renderMathInElement(document.getElementsByClassName("katex-inner"))$
Write out in full the strings $0^5, 0^31^3, (010)^2, (01)^30, 1^0$
Solution ▾
$$00000, 000111, 010010, 0101010, \epsilon$ $\\$ renderMathInElement(document.getElementsByClassName("katex-inner"))$

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\} $

Simplified forms ▾

\(L_1 = \{0,1,00,11,000,111,...\}\) , \(\\\) \(L_2 = \{0,1\}^* = \{\epsilon,0,1,00,11,01,10,000,111,010,011,100,101,... \}\) , \(\\\) \(L_3= \{w \mid w \in \Sigma^*, |w|=1\} = \{0,1\}\) , \(\\\) \(L_4=\{w \mid w \in \Sigma^*, |w|=2\} = \{00,11,01,10\}\) , \(\\\) \(L_5=\{w \mid w \in \Sigma^*, |w| \geq 1\} = \{0,1,00,11,01,10,000,111,010,011,100,101,...\} = L_2 \backslash \ \{\epsilon\}\) \(\\\) renderMathInElement(document.getElementsByClassName("katex-inner"))

$ 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\} $ renderMathInElement(document.getElementsByClassName("katex-inner"))$
$ 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$ $\\$ renderMathInElement(document.getElementsByClassName("katex-inner"))$
$ 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\}$ $\\$ renderMathInElement(document.getElementsByClassName("katex-inner"))$
$ \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\}$ $\\$ renderMathInElement(document.getElementsByClassName("katex-inner"))$
$ 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\}$ $\\$ renderMathInElement(document.getElementsByClassName("katex-inner"))$
$ 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} \}$ $\\$ renderMathInElement(document.getElementsByClassName("katex-inner"))$