Automata and Formal Languages - CSI3109
This post retrived from CSI3109 Yonsei University 2023-spring
Used text book : Introduction to Automata Theory, Languages, and Computation (3rd edition) by John E. Hopcroft,, Rajeev Motwani and Jeffery D. Ullman

What we will learn?

Formal language and automata theory. Fundamental knowledge on computation and computability. Finite-state automata andPushdown automata, Turing machines.

• Finite-state automata : Regular Languages
• Context-free automata : Context-free languages
• Turing machine : Unrestricted languages

We can understand each pairs' meaning as Computability.
So, we learn Mathematical study of computing machines, their fundamental capabilities and their limitations.

More...
What problem can be solved (computed) , in PRINCIPLE and in PRACTICE, by computer and what problems cannot?
Computability theory for first one, Complexity theory(Algorithm Design Area) for second one.

Examples of UNSOLVABLE problems

• Given two programs, determine whether or not they compute the same function.
• The general problem of whether or not a program terminates under all inputs.

Terms

Alphabets, Strings and Languages

Alphabets

Finite, nonempty set of symbols.
Denoted by $\Sigma$.

Strings

Finite sequence of symbols from Alphabet.
Denoted usually by $w$
Empty string is the string with zero occurrences of symbols.
Denoted by $\lambda$.
Length of string $w$ is denoted by |$w$|
Occurrence $|w|_{\sigma}$ is the number of occurrence of $\sigma$ in $w$.
Power $\Sigma^{k}$ of an alphabet is the set of strings of length $k$.
The set of all strings over $\Sigma$ is denoted by $\Sigma^{*}$.
$\Sigma^* - {\lambda}$ = $\Sigma^+$
$w_x \cdot w_y$ means concatenation of given two string $w_x$ and $w_y$.
* $\lambda w = w\lambda = w$

Languages

Set of strings all of which are chosen from $\Sigma^*$.
$L \subseteq \Sigma^*$
$\empty$ is empty languages over any alphabets.

Some notations and definitions about SETs

Power set

$2^A$ : The set of all subsets of a set $A$ is the power set of $A$.
e.g $2^{a,b}$ = $\{ \empty , \{a\}, \{b\} \{a,b\}\}$

---

Partition

A partition of $A$ is any set $\{A_1, A_2, ... \}$ of nonempty subsets of $A$ such that
1. $A = A_1 \cup A_2 \cup ...$ and
2. $A_i \cap A_j = \empty$ for all $i \neq j$.

---

Cartesian Product and Functions

$A \times B$ of two sets $A$ and $B$ is the set of all possible ordered pairs $(a,b)$ with $a \in A$ and $b \in B$.

---

Function

$f : A \rightarrow B$, is a binary relation $R$ on $A$ and $B$ such that, for each $a \in A$, if $(a,b) \in R$ and $(a,c) \in R$, then $b = c$ and, for each $a \in A$, there is either exactly one $b \in B$ such that $f(a) = b$ or there is no $b \in B$ such that $f(a) = b$. Such a function is said to be a partial function.
If $\forall a \in A$, there is $b \in B$ such that $f(a) = b$, we call $f$ as total

---

$f : A \rightarrow B$ is ${\color{red}\texttt{one-to-one}}$ if, for any distinct $a, a' \in A$, $f(a) \neq f(a')$.
$f : A \rightarrow B$ is ${\color{red}\texttt{onto}}$ if, for all $b \in B$, there is some $a \in A$ such that $f(a) = b$.
A total function $f$ is ${\color{red} \texttt{bijection}}$ if it is both one-to-one and onto.