Welcome to CS 4410,
Automata, Computability, and Formal Languages
Course Description
University Catalog:
Finite state concepts; sequential machines and state minimization;
Chomsky grammar; algorithms on grammars; computability and Turing
machines; non-computable functions.
This course is designed to provide students with an understanding of
the basic concepts in the theory of computation. Using precise
mathematical reasoning we seek to understand what can be computed
and with what degree of difficulty. This will lead us to identify
classes of problems that can be addressed using general algorithmic
approaches, which has practical applications (for example in
programming languages and compiler construction). We will also study
the representations for languages and their correspondence to
machines.
By the end of the course, a student will be able to:
Construct a finite state machine and the equivalent regular
expression.
Prove the equivalence of languages described by finite state
machines, regular grammars and regular expressions.
Construct pushdown automata and the equivalent context-free
grammars.
Prove the equivalence of languages described by pushdown
automata and context-free grammars.
Please note that I may sometime
have to reschedule or cancel office hours. If I do I will post
in the Announcements and/or send email.
Zoom link is in Canvas on the Home page.
Monday
3-4pm
Zoom
Tuesday
3-4pm
Zoom
Friday
noon-1pm
DBH
278
And
by appointment
Best way to contact Dr. Martin: Email
mmartin@csustan.edu Please put "CS4410" in the subject line of
the email.
Prerequisite: CS 3100
and Math 2300 - please see me if you do not meet the prerequisites
Warning: I reserve the right to make changes to the
syllabus at any time during the term by announcing them in class
and on my web page.
Health and Safety
This course is designed to be an in-person and will meet in
Bizzini 111. There may be some days may be online: some may
synchronous.
If you are unable to attend class on an in-person day, you should
email me prior to class time. You may be required to provide a
doctor's note or other evidence of the necessity of the absence.
Grading and Policies
Final grades will be based on homework, reaction papers,
participation and quizzes or the final exam. A plus and minus
grading scale will be used to assign final grades.
Homework, Reaction Papers:
In order to understand the topics and concepts we are discussing in
class, it is necessary to practice. We will use a combination of
homework and reaction papers, to make sure that everyone is keeping
up and understanding the material. We will have a combination of
group work and class discussions of problems in class.
Submission of Homework: All
homework (unless otherwise stated) are to be turned as follows:
All assignments should be in the form of pdf files uploaded to
Canvas. Reaction papers may be files in a text, or Word, or pdf
format.
Participation: Coming to
class and participating in discussion and problem sessions is
important to understand the concepts we are learning and to be able
to complete assignments. Participation will account for 10% of your
grade.
Quizzes and Exam: There will
be at least 5 quizzes. You may take the final exam, comprised of
problems similar the the quiz problems, the higher score will
account for 45% of your final grade. Grade Summary:
Homework,
reaction papers
45%
Participation
10%
Quizzes
or Final Exam (highest score)
45%
Total
100%
Academic Honesty: The work you do for this course will be
your own, unless otherwise specified. You are not to submit other
people's or machine's work and represent it as your own. I
consider academic honesty to be at the core of the University's
activities in education and research. Academic honesty is expected
at all times in this course.
Attendance: Regular class attendance is expected; we
will do work in class that will count toward your grade. Students
are responsible for all announcements and in-class discussion.Please
email me in advance and follow up in person if you know you will
need to miss class.
Collaboration and Teamwork: On some assignments students may
be encouraged to co-operate by discussing the problems. That does
not mean labor division in terms of problem solutions. All problems
for all assignments must be done by the student who is submitting
the assignment. Copying someone else's work OR allowing someone to
copy your work are prohibited. All discussions and other aids used
must be explicitly and properly acknowledged. For instance (examples
based on Vadim Bulitko's http://www.cs.ualberta.ca/~bulitko/W04):
"I discussed problem 3.43 with my
classmates K. Black and P. Posey. On problem 3.49 I received an
office-hour consultation from my instructor R. Altman.
Additionally I used sources [1] and [2] for problem 3.78.
[1]. A.Jolie. "Fast Numeric Methods for Curvature
Approximation", Journal of Geeky Gamers, volume 36, issue C,
June 2001.
[2] F.Oz. "On Using the Force as a Theorem Proving Technique",
Jedi Archives, volume 666, number 34, May 2002."
Any unacknowledged aid (e.g., copying from other students, copying
from external sources, or elsewhere) constitutes a case of
plagiarism.
Any use of AI, must be cited and the prompt included to avoid
plagiarism. In addition, anything produced by an AI must be fact
checked and the fact checking documented.
Cell Phone Policy: During class time, your cell phone
(including headsets) must be turned off and out of sight. Any use of
a cell phone during class will result in confiscation of the phone
until that day's class has ended or your removal from the class for
that day. If you attempt to use your cell phone or leave it on
during an exam, you will be considered to have finished your test,
and I will collect your exam at that time. Exceptions may be
made only if you discuss your situation with me prior to the start
of that day's class, in this case, your cell phone must be set to
vibrate/silence.
University Recording Policy: Audio or video recording (or any
other form of recording) of classes is not permitted unless
expressly allowed by the faculty member as indicated in the course
syllabus or as a special accommodation for students who are
currently registered with the Disability Resource Services Program
and are approved for this accommodation. Recordings allowed as
special accommodations are for the personal use of the DRS-approved
student, and may only be distributed to other persons who have been
approved by the DRS program. Faculty may require the student sign an
Audio/Video Recording Agreement, which they may keep for their
records.
University Disability Services:CSU Stanislaus respects all forms of diversity.
By university commitment and by law, students with
disabilities are entitled to participate in academic activities and
to be tested in a manner that accurately assesses their knowledge
and skills. They also may qualify for reasonable accommodations that
ensure equal access to lectures, labs, films, and other
class-related activities. Please see the instructor if
you need accommodations for a registered disability. Students
can contact the Disability Resource Services office for additional
information. The Disability Resource Services website can be
accessed at http://www.csustan.edu/DRS/
Phone: (209) 667-3159 Important dates: