Fall 2023
CS3613: Theory of Automata &
Formal Languages
Mr. Hashim Ayub
About the Course & Text Book
Class Schedule
– Tuesday & Friday (Check your time-table:)
Consult course page on Portal and Network Folder for
– Lecture Notes, Quizzes, Assignments & Term Project
Text Book:
• Michael Sipser, “Introduction to the Theory of Computation”, 3rd Ed.,
Cengage Learning, 2013
Reference Books:
• John C. Martin, “Introduction to Languages and the Theory of
Computation”, 4th Ed., McGraw Hill, 2011
• J.E. Hopcroft, R. Motwani and J.D. Ullman, “Introduction to Automata
Theory, Languages and Computation”, 2nd Ed., Addison-Wesley 2001
• Elaine A. Rich “Automata, Computability and Complexity: Theory and
Applications”, Prentice Hall, 2013
2
Assessment Plan
• Assessment (Tentative Plan)
– 20% Quizzes (04 at-least, Full of Surprise)
– 20% Assignments (04 at-least, individual)
– 20% Midterm Exam
– 40% Final Exam
3
Assignment Policy
• In order to develop comprehensive understanding of
the subject, assignments will be given.
• Late assignments (by up to 2 days) will be accepted but
penalized as per the following formula:
• Less than a day late: 20% penalty
• More than 1 day late but less than 2 days late: 40%
penalty
• More than 2 days late: not accepted.
4
General Topics
• Abstract machine models of computation (e.g.,
DFA, NFA, TM).
• Classes of grammars (e.g., regular grammars,
context-free grammars, context sensitive
grammars, unrestricted grammars).
• Classes of formal languages (e.g., regular, context-
free, context-sensitive, recursive, recursively
enumerable).
• Relationships between the languages, grammars
and machines. 5
Practical
Application/Relevance
• Pattern matching
– Bioinformatics
– Lexical analysis
• Design and Verification
– Hardware & Software
– Communication Protocols
• Parsing Languages
– Compiler construction
– Natural language processing, Machine Translation
• Algorithm design and analysis
6
Theory of Automata?
• Automata is a Greek word which means “Self
Acting”
• Automata theory is the study of abstract
machine.
• An abstract machine, also called an abstract
computer, is a theoretical model of a
computer hardware or software system used
in automat theory.
7
Letter or Symbol
Any single object or character or integer is called
letter or Symbol
For example:
• 1
• A
• @
• #
8
Alphabets
We define an alphabet to be any non-empty
finite set of symbols or letters, usually denoted
by Σ (Sigma).
Examples:
Σ1= {0 1}
Σ2= {a b c… x y z}
Σ1 and Σ 2 are two alphabets
0, 1, a, b, c… are called letters or symbols
9
Strings
String is combination of symbols taken from set of
alphabets.
For Example:
• Σ2= {a b c… x y z}
• Now string is (abc, abd, xyz… etc)
• A word is a combination of symbols taken from
set of alphabets which gives us meaning.
• For example book, flight etc.
• The empty string contains no letters and is
written as λ or ε.
10
Languages
A language L is a set of strings.
• For example, if Σ = {a b}
L1 = { } No word, so it an empty language
L2 = {ε} Not an Empty Language
L3 = {a aa aaa} finite set
L4 = {a aa aaa….} infinite set
11
A real world example
• The controller of an automatic door is one
example of such finite automaton [Sipser07]
front Pad rear pad
door
Fig. Top-down view of an automatic door
12
Questions?
Thank You!