Fall 2025
CS3613: Theory of Automata &
Formal Languages
Ms. Aysha Nabeel
Contact:
[Link]@[Link]
About the Course & Text Book
Class Schedule
– Monday & Wednesday (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)
– 15% Quizzes (04 at-least)
– 15% Assignments (04 at-least, individual)
– 10% Project
– 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
Intro to Theory of Automata
• Automata theory studies mathematical
models of computation.
• These models are applied in several areas of
computer science.
• Finite Automaton → used in text processing,
compilers, hardware design.
• Context-Free Grammar → used in
programming languages & AI.
8
What is a Set?
A set is a group of objects represented as a unit.
Objects inside a set are called elements or
members.
For example:
• 7∈S (7 is in S)
• (8 is not in S)
9
Types of Sets
Empty set (∅) → no elements
Singleton → one element
Subset (⊆) → all elements of A are in B
Proper Subset (⊂) → A is in B but not equal to B
Infinite set → continues forever (e.g. )
10
Set Operation
• Union (A ∪ B): elements in A or B
• Intersection (A ∩ B): elements common to A
and B
• Complement (A̅): all elements not in A
• Venn diagrams show these relations
11
Sequence & Tuples
• A sequence = ordered list (order matters,
repetition matters).
• Example: (7, 21, 57) ≠ (57, 7, 21)
• Tuples: finite sequences
• (7, 21, 57) → 3-tuple
• (a, b) → ordered pair (2-tuple)
12
Cartesian Product
• Combination of two sets into ordered pairs.
• Example:
• A = {1,2}, B = {x,y}
• A × B = {(1,x), (1,y), (2,x), (2,y)}
13
Functions
A function maps input → output.
Same input always gives same output.
Example: Notation:
Domain = input set
Range = output set
14
Predicates & Relations
• A predicate (or property) is a function whose
range is {TRUE, FALSE}.
• Example:
• even(4) = TRUE
• even(5) = FALSE
• A relation is a predicate defined over k-tuples
(A × … × A).
15
Letter or Symbol
Any single object or character or integer is called
letter or Symbol
For example:
• 1
• A
• @
• #
16
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
17
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 .
18
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
19
Kleen Closure
In automata theory, closure (sometimes called
Kleene closure or Kleene star) is an operation
applied to an alphabet or a set of strings. It
describes the idea of repeating symbols or strings
any number of times, including zero times.
• Think of closure like “looping” or “repetition”:
• Kleene star (*) → "zero or more times"
• Kleene plus (+) → "one or more times"
20
Kleen Closure
Example:
• Let Σ = {0, 1}
• Σ* = { ε, 0, 1, 00, 01, 10, 11, 000, 001, … }
(all binary strings, including the empty string ε)
• Σ⁺ = { 0, 1, 00, 01, 10, 11, 000, … }
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
22
Questions?
Thank You!