Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456 Syntax and Semantics
After an introduction to the contents of this course, we begin our
investigation of the topics covered in the part of the course dealing
with Syntax. Our main topics of interest over the first seven
lectures will be strings and languages. We shall
then introduce the formalism of finite automata, and begin to
study some of its properties and its computational power.
Finite automata are our first example of abstract
machine. Abstract machines are mathematical models of
computational devices, and we shall characterize their expressive
power in terms of the collection of languages that they recognize. The
languages recognized by finite automata are called
regular.
Whenever you construct an automaton, try to argue that it does the job
that it was meant to do. You may not need (some of) the material
covered in this course in your future careers, but having an
analytical and critical attitude will always help you.
Let Sigma be an alphabet. What language do we obtain by
concatenating Sigma* with itself? What if we do the same with Sigma+?
Argue for your answers.
Exercises 1.1(*), 1.2, 1.4(a)(*), 1.4(d)(*) and 1.4(j)(*) on pages
83-84 of
Introduction to the Theory of Computation by Michael Sipser. (You are
encouraged to try to solve more of the sub-items in exercise 1.4, if
you have time.)
(*) Prove that if L is regular, then so is its complement.
Prove that if L and M are regular, then so it the intersection of
L and M.
[Programming Exercise] Write a simulator for deterministic
finite automata in your favourite programming language. The program
should allow the user to input an automaton to be simulated, and the
input on which to carry out the simulation. It should also be possible
to save automata, and load already saved ones.