Tutorial 01 - Introduction

Outline

A review on essential mathematical concepts and an overview on languages.

countability: an overview of definitions
set theory: a review on set theory and describing sets
proof types: proof by contradiction, contrapositive, induction, and construction
languages: a review on alphabets, symbols, strings, etc..

Countability

finite: we can count the elements up to some number $n$
countably infinite: we can map to $\mathbb{N}$, the set of natural numbers
uncountably infinite: there exists no way of counting that maps to $\mathbb{N}$

Set Theory

A Few Basic Definitions

set: $S = \{a, b, c, d\}$
membership: $a \in S$, $f \not\in S$
empty set: $\emptyset$
singleton set: set with exactly 1 element
unordered pair set: set with 2 elements

A Few Basic Definitions

union: $A \cup B$
intersection $A \cap B$
complement: $\bar{A}$
set difference: $A - B$
cartesian / cross product: $A \times B$

Describing Sets

Describe the following set in plain English:

\[\{x | x = 2m \text{ for each m in } \mathbb{N}, m > 5\}\]

Writing Sets

Write the following sets in set notation:

The set of all integers greater than 5.
The set of all strings $00 \cdots 001 \cdots 1$ where all 0’s come before 1’s and there are twice as many 0’s as 1’s.
The set of all odd number $\geq 1$.

Proof Types

Contradiction

\[\text{Prove that $\sqrt{2}$ is an irrational number by contradiction.}\]

Remember: You’ll want to state your goal (i.e., prove that $\sqrt{2}$ is an irrational number). You’ll then want to assume the opposite (i.e., assume that $\sqrt{2}$ is a rational number). And finally, you’ll want to draw a conclusion that results in a contradiction (i.e., a statement that contradicts $\sqrt{2}$ is a rational number). Lastly, you’ll need to write a formal conclusion.

Contrapositive

Let us consider the following $p \longrightarrow q$ where we want to prove $\urcorner q \longrightarrow \urcorner p$.

Example

Prove that for any integer $n$, if $n^{2}$ is even then $n$ is even.

Suppose $n$ is odd.
Prove that $n^{2}$ is odd.

Induction

Example

Prove that $1 + 2 + \cdots + n = n(n+1)/2$.

Prove the base case(s).
State the inductive hypothesis.
Perform the inductive step(s).
Write a formal conclusion.

Construction

Theorems often state that an object exists. Proof by Construction is a way to prove the theorem by constructing the object (i.e., proof by look here’s one).

Example

Prove that there is a program that can be used to calculate $A + B$.

Write a program that can calculate $A + B$.

Languages - Review

Informally

Alphabets and Languages will be key components of this course.

alphabets are a set of symbols, just as you know from daily life
- for example, the alphabet for English is $\{a, b, c, \cdots, z\}$
- while the alphabet for German is $\{a, b, c, \cdots, \beta, z, \text{ü}, \text{ö}, \text{ä}\}$
similarly, language are a set of words (strings) made up from a given alphabet
- for example, the English language contains words like "hello", "goodbye"
- and the French language contains words like "bonjour", "chat"

Note: Even when given the exact same alphabet, you can create different languages.

Formally

a language is a set of strings
an alphabet is a finite set of symbols denoted $\Sigma$
a string is any combination of symbols in $\Sigma$
empty string = $\epsilon$
set of all strings of an alphabet is $\Sigma^{\ast}$
length of strings, $|\epsilon| = 0$, if $w = ab$, then $|w| = 2$
position, $w = aba$, then $w_{2} = b$, and $w_{1} = w_{3} = a$
concatenation, $x = hi$ and $y = bye$, then $xy = hibye$

Languages

Kleene star, $L^{\ast}$, is the concatenation of all substrings of $L$ with $L$ (infinite).

Example

Consider the following:

\[L_{1} = \{00, 11\}\]

then

\[L_{1}^{\ast} = \{\epsilon, 00, 11, 0011, 1100, \cdots\}\]

where $\ast$ means 0 or more occurrences

\[L_{1}^{+} = \{00, 11, 0011, 1100, \cdots\}\]

and where $+$ means at least 1 occurrence.

Tutorial 02 - DFA, NFA, Union, and Kleene Star

Question - 2.1

Give the formal specification of a Deterministic Finite Automata (DFA) for the following language:

\[L = \{0\}^{\ast} \text{ over } \Sigma = \{0\}\]

Question 2.2

Give the formal specification of a DFA for the following language:

\[L = \{w \in \{a, b\}^{\ast} | w \text{ is any string not in } (ab^{+})^{\ast}\}\]

Question 2.3

Consider the following state diagram:

where the start state is $B$, and state $A$ and state $D$ are accept states

and is described by the following transition table:

State Diagram - Transition Table
$\delta$	$0$	$1$	$\epsilon$
$A$	$\emptyset$	$A$	$B$
$B$	$\emptyset$	$\emptyset$	$\{A, C\}$
$C$	$\{C, D\}$	$C$	$\emptyset$
$D$	$\emptyset$	$\emptyset$	$\emptyset$

(a) Is the string 0011 accepted by this state machine? How about 1100?

(b) What is the language of this machine?

Question 2.4

Design an Non-Deterministic Finite Automata (NFA) state diagram for the following language:

\[\{w \in \{0, 1\}^{\ast} | w \text{ contains } 00 \text{ or } 11 \text{ as a substring}\}\]

DFA Union Closure

Regular languages are closed under union.

What does "closed" mean?

A set $S$ is closed under operation $O$ if $O(S) \in S$.

Let $S = \{a, b, c\}$. Define $O$ as such: $O(a) = b$, $O(b) = c$, and $O(c) = a$.

Notice that applying $O$ yields elements that are all in set $S$. So $S$ is closed under $O$. If $O$ were defined the same but $O(c) = z$, then $S$ is no longer closed under $O$.

Kleene Star Proof

Prove that regular languages are closed under Kleene star.

Reduction Discussion

Reduction...

Problem A: Will Ammar Brush His Hair?

Problem B: Is Angela Happy?

Reduction:

\[A \longrightarrow B\]

"A reduces to B"

The outcome of $A$ relies on the outcome of $B$.

Tutorial 03 - Regular Expressions

Question 3.1

Design a regular expression for the following languages over the alphabet $\Sigma = \{0, 1\}$:

(a) $L_{1} = \{w | \text{every odd position of } w \text{ is a } 1\}$

(b) $L_{2} = \{w | w \text{ is a string of length at most } 5\}$

(c) $L_{3} = \{w | w \text{ contains an even number of } 0 \text{'s or exactly two } 1 \text{'s}\}$

Question 3.2

Convert the following regular expression to an NFA:

\[R_{1} = (a \cup b^{\ast})a\]

DFA to Regular Expression

If a language is regular, then there exists some regular expression that describes it.

Transform the following Deterministic Finite Automata (DFA) into a Regular Expression:

DFA

where the DFA can be describe by the following:

\[DFA = (\{q_1, q_2\}, \{a, b\}, \delta, q_1, \{q_2\})\]

and $\delta$ is defined as:

DFA - Transition Table
$\delta$	$a$	$b$
$q_1$	$q_1$	$q_2$
$q_2$	$q_1$	$q_2$

Tutorial 04 - Pumping Lemma

Question 4.1

Prove that the following language is not regular using the pumping lemma.

\[L_{1} = \{0^{n}1^{n}2^{n} | n \geq 0\}\]

Question 4.2

Prove that the following language is not regular using the pumping lemma.

\[L_{2} = \{w^{r}w | w \in \{0, 1\}^{\ast}\}\]

Reflection on Question 4.2

Why is the string $s = 0^{P}0^{P}$ not a good choice to devise a contradiction to prove $L_{2}$ is not regular?

Tutorial 05 - CFG, and CNF

Question 5.1

Consider the following language over $\Sigma = \{0, 1\}$, find a set of rules that defines a Context Free Grammar (CFG) that recognizes the language:

\[L_{1} = \{0^{n}1^{n} | n \geq 0\} \cup \{1^{n}0^{n} | n \geq 1\}\]

Question 5.2

Consider the following language over $\Sigma = \{0, 1\}$, find a set of rules that defines a CFG that recognizes the language:

\[L_{2} = \{w | w \text{ starts and ends with the same symbol}\}\]

Question 5.3

Consider the following language over $\Sigma = \{0, 1\}$, find a set of rules that defines a CFG that recognizes the language:

\[L_{3} = \emptyset\]

Question 5.4

Consider the following language over $\Sigma = \{0, 1\}$, find a set of rules that defines a CFG that recognizes the language:

\[L_{4} = \{w | w \text{ contains at least three } 1 \text{s}\}\]

Question 5.5

Consider the following language over $\Sigma = \{0, 1\}$, find a set of rules that defines a CFG that recognizes the language:

\[L_{5} = \{0^{n}1^{m} | 2n \leq m \leq 3n\}\]

Question 5.6

Consider the following language over $\Sigma = \{0, 1\}$, create a parse tree and show sequence derivations for the string $000111$:

\[L_{6} = \{0^{n}1^{n} | n \geq 0\}\]

Question 5.7

Derive or generate the string "aabaa" for the following grammar:

\[\begin{aligned} S &\longrightarrow aAS | aSS | \epsilon \\ A &\longrightarrow SbA | ba \end{aligned}\]

Question 5.8

Convert the following CFG into Chomsky Normal Form (CNF):

\[\begin{aligned} S & \longrightarrow ASB \\ A & \longrightarrow aAS | a | \epsilon \\ B & \longrightarrow SbS | A | bb \end{aligned}\]

Question 5.9

Convert the following CFG into CNF:

\[\begin{aligned} S & \longrightarrow aXbX \\ X & \longrightarrow aY | bY | \epsilon \\ B & \longrightarrow X | c \end{aligned}\]

Question 5.10

Convert the following CFG into CNF:

\[\begin{aligned} S &\longrightarrow AAA | \epsilon \\ A &\longrightarrow aa | Aa | \epsilon \end{aligned}\]

Question 5.11

Complete the state diagram by adding missing transitions so that it describes a Push Down Automata (PDA) that recognizes the following language:

\[L = \{a^{m}b^{n} | m,n \geq 0 \text{ and (either } m = n \text{ or } m = n + 2 \text{)}\}\]

where the start state is $s_1$, and state $s_6$ is the accept state

and is described by the following transition table:

PDA - Transition Table
State	Input Symbol	Stack Symbol	Next State	Stack Operation
$s_1$			$s_2$
$s_1$			$s_3$
$s_2$			$s_2$
$s_2$			$s_4$
$s_3$			$s_3$
$s_3$			$s_5$
$s_4$			$s_4$
$s_4$	$\epsilon$	$\$$	$s_6$	$\epsilon$
$s_5$			$s_4$

Question 5.12

Prove or disprove that every subset of a Context Free Language (CFL) is a regular language.

Tutorial 06 - CFL Pumping Lemma, and TM

Question 6.1

Show that the following language is not a Context Free Language (CFL) using the CFL pumping lemma:

\[A = \{a^ib^jc^k | 0 \leq i \leq j \leq k\}\]

Question 6.2

Show that the following language is not CFL using the CFL pumping lemma:

\[B = \{0^{n} \# 0^{2n} \# 0^{3n}| n \geq 0\}\]

Question 6.3

Give a high level description of a Turing Machine which decides:

\[C = \{0^{2^{n}} | n \geq 0\}\]

Hint: Review page 143 in the Textbook.

Tutorial 07 - PDA, TM

Question 7.1

Construct a Push Down Automata (PDA) from the following Context Free Grammar (CFG):

\[S \longrightarrow S1 | 1S0S | \epsilon\]

Question 7.2

Give a high level description of a Turing Machine which decides:

\[A = \{0^{2^{n}} | n \geq 0\}\]

Question 7.3

Give a high level description of a Turing Machine which decides:

\[B = \{a^ib^jc^k | i \times j = k \text{ and } i, j, k \geq 1\}\]

Question 7.4

Give a high level description of a 2-tape Turing Machine which recognizes the language (binary palindromes):

\[L = \{w \in \{0, 1\}^{\ast} | w = w^r\}\]