0

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

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**.

Finite, nonempty set of symbols.

Denoted by $\Sigma$.

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$

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, ... \}$ ofnonemptysubsets 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

allpossible 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$ astotal

$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.