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.
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
Finite, nonempty set of symbols.
Denoted by .
Finite sequence of symbols from Alphabet.
Denoted usually by
Empty string is the string with zero occurrences of symbols.
Denoted by .
Length of string is denoted by ||
Occurrence is the number of occurrence of in .
Power of an alphabet is the set of strings of length .
The set of all strings over is denoted by .
means concatenation of given two string and .
Set of strings all of which are chosen from .
is empty languages over any alphabets.
Some notations and definitions about SETs
: The set of all subsets of a set is the power set of .
A partition of is any set of nonempty subsets of such that
2. for all .
Cartesian Product and Functions
of two sets and is the set of all possible ordered pairs with and .
, is a binary relation on and such that, for each , if and , then and, for each , there is either exactly one such that or there is no such that . Such a function is said to be a partial function.
If , there is such that , we call as total
is if, for any distinct , .
is if, for all , there is some such that .
A total function is if it is both one-to-one and onto.