|
|
Formal Languages and Computability
(csc360)
Fall 2020
Dr. Gur Saran Adhar
Module One: Review (Text: Chapters
1 and 2)
This
course is about mathematical models of computers and algorithms. The purpose
of this module is to review concepts and techniques for the study of
theoretical computer science, in particular, of formal languages and
machines.
The mathematical study of computation begins by understanding the mathematics
of strings of symbols. An alphabet is a finite string of symbols. A string
over an alphabet is a finite sequence of symbols from the alphabet. To
write a string, we simply juxtapose the symbols; thus, 0001001 is a string
over the alphabet {0,1}. A string with no symbols is called the empty
string and is denoted by the Greek symbol lambda. The set of all finite
strings over an alphabet E is denoted by E*. The length of a string is the
number of symbols it has. We can define other operations on strings like concatenation
and reversal.
A central
issue in the theory of computation is the representation of languages by
finite specifications. The first example we use is regular expressions .
Regular languages are sets of strings that can be expressed as regular
expressions.
By the end of this module, you should be refreshed in the knowledge of the
following:
- Sets, relations and functions
- Cardinality of sets; the difference between countable
and uncountable sets.
- Recursive definitions of sets;
- Mathematical induction as a proof technique;
- The diagonalization proof that a set is not
countable; Example
- Strings and Languages; finite specifications of
languages using regular sets and expressions;
Regular Expressions at Work
|
