Automata and Formal Languages - Introduction

kjh_b_d·2023년 3월 23일

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.

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.


Alphabets, Strings and Languages


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


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


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

Some notations and definitions about SETs

Power set

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


A partition of AA is any set {A1,A2,...}\{A_1, A_2, ... \} of nonempty subsets of AA such that
1. A=A1A2...A = A_1 \cup A_2 \cup ... and
2. AiAj=A_i \cap A_j = \empty for all iji \neq j.

Cartesian Product and Functions

A×BA \times B of two sets AA and BB is the set of all possible ordered pairs (a,b)(a,b) with aAa \in A and bBb \in B.


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

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

0개의 댓글