CS5113

Advanced Theory of Computation

DR. AAMER NADEEM
LECTURE 01 – MAR. 04, 2024

CAPITAL UNIVERSITY OF SCIENCE AND TECHNOLOGY

ABOUT THE COURSE
Course Code: CS5113
Course Title: Advanced Theory of Computation
Pre-requisite: Theory of Automata and Formal Languages
Category: Core Course in MS(CS) program
Class timings:
Every Monday 6:00 PM to 7:20 PM
and 7:30 PM to 8:50 PM

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2024 2

ABOUT THE INSTRUCTOR
Name: Dr. Aamer Nadeem
Office Location: 1st Floor, Block M
How to Contact:
By visiting the office
By email: anadeem@cust.edu.pk
On Microsoft Teams
Areas of Interest:
- AI and Machine Learning
- Formal Methods and Software Reliability
CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2024 3
EVALUATION CRITERIA

Quizzes 20%
Assignments 20%
Midterm Exam 20%
Final Exam 40%
Total 100%

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2024 4

Recommended Books (1)
1. Introduction to Languages and the
Theory of Computation (4th Edition)

By: John C. Martin

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2024 5

Recommended Books (2)
2. Languages and Machines: An
Introduction to the Theory of
Computer Science (3rd Edition)

By: Thomas A. Sudkamp

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2024 6

Recommended Books (3)
3. Introduction to Computer Theory
(2nd Edition)

By: Daniel I.A. Cohen

(For Pre-requisite course)

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2024 7

Course Learning Outcomes (CLOs)
1. Model a decision problem as a formal language
2. Prove decidability or undecidability of a decision problem

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2024 8

Computational Problems
• A computational problem is a problem that may possibly be solved
by an algorithm
• There are two types of computational problems:
• Decision Problems
• Function Problems

• In decision problems, the solution is binary, i.e., in the form of

yes/no, true/false or 1/0
• In function problems, the solution is usually more complex
• Every function problem can be converted to a decision problem

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2024 9

Function Problems – Examples
1. Given a positive integer 𝑛, find all prime factors of 𝑛
2. Given two positive integers 𝑎 and 𝑏, find greatest common divisor
(GCD) of 𝑎 and 𝑏?
3. Given two positive integers 𝑖 and 𝑗, find all prime numbers 𝑝 such
that 𝑖 ≤ 𝑝 ≤ 𝑗
4. Given a multivariate polynomial, what are its roots?
5. Given two square matrices of size 𝑛 × 𝑛, what is their product?
6. Given a graph G and two nodes of the graph 𝑖 and 𝑗, find a path
from 𝑖 to 𝑗

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2024 10

Decision Problems – Examples
1. Given a positive integer 𝑛, is 𝑛 a prime number?
2. Does a given quadratic equation have integer roots?
3. Does a given polynomial of one variable have integer roots?
4. Does a given multivariate polynomial have integer roots?
5. Matrix Mortality Problem: Given a finite set of 𝑛 × 𝑛 matrices, does
any finite product of matrices, possibly with repetition equals zero
matrix?
6. Can a given integer 𝑛 be expressed as sum of cubes of 3 integers?
That is,
𝑛 = 𝑎3 + 𝑏 3 + 𝑐 3

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2024 11

Decidable and Undecidable Problems
• A decision problem is called decidable if an algorithm exists that
• Takes inputs of the problem
• Produces output yes or no for the given input

• If no algorithm exists to solve a decision problem, the problem is

called undecidable
• For example, Matrix mortality problem is undecidable

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2024 12

Languages
Languages
• Definition: A language is a set of strings, called words
• Words of a language are formed by combining zero or more alphabet
symbols from the alphabet set of the language
• Examples:
Σ = {𝑎 𝑏}
𝐿1 = {𝑎𝑏 𝑏𝑏}
𝐿2 = {𝑎𝑏 𝑏𝑎}
𝐿3 = {𝑎 𝑎𝑎 𝑎𝑎𝑎 𝑎𝑎𝑎𝑎 … … }
𝐿4 = {𝑏𝑎 𝑏𝑎𝑎 𝑏𝑎𝑎𝑎 𝑏𝑎𝑎𝑎𝑎 … … }

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2024 14

Languages (2)
• A language can be empty or non-empty
• A language can be finite or infinite
• The length of a word defined as the number of alphabet symbols in
the word
• The length of a word can be zero or more
• Length zero word is denoted by the special symbol 𝜀 (epsilon)

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2024 15

Languages (3)
• Examples:
Σ = {𝑎 𝑏}
𝐿1 = {𝑎𝑏 𝑏𝑎 𝑏𝑏}
𝐿2 = {𝜀 𝑎 𝑎𝑎}
𝐿3 = {𝑏 𝑎𝑏 𝑎𝑎𝑏 𝑎𝑎𝑎𝑏 𝑎𝑎𝑎𝑎𝑏 … … }
𝐿4 = {𝜀}
𝐿5 = { }
𝐿6 = {𝑎𝑏 𝑎𝑏𝑎𝑏 𝑎𝑏𝑎𝑏𝑎𝑏 𝑎𝑏𝑎𝑏𝑎𝑏𝑎𝑏 … … }

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2024 16

Kleene Closure
• Kleene Closure Language: The language of all possible strings over a
given alphabet set is called Kleene Closure and is denoted by Σ ∗
• Example 1
Σ = {𝑎}
Σ ∗ = {𝜀 𝑎 𝑎𝑎 𝑎𝑎𝑎 𝑎𝑎𝑎𝑎 … … }
• Example 2
Σ = {𝑎 𝑏}
Σ ∗ = {𝜀 𝑎 𝑏 𝑎𝑎 𝑎𝑏 𝑏𝑎 𝑏𝑏 𝑎𝑎𝑎 𝑎𝑎𝑏 … … }

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2022 17

Positive Closure
• Positive Closure Language: The language of all possible strings
formed by combining one or more alphabet symbols is called Positive
Closure and is denoted by Σ +
• Example 1
Σ = {𝑎}
Σ + = {𝑎 𝑎𝑎 𝑎𝑎𝑎 𝑎𝑎𝑎𝑎 … … }
• Example 2
Σ = {𝑎 𝑏}
Σ + = {𝑎 𝑏 𝑎𝑎 𝑎𝑏 𝑏𝑎 𝑏𝑏 𝑎𝑎𝑎 𝑎𝑎𝑏 … … }

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2022 18

Lexicographic Order
• Lexicographic order is usually followed to write words of a language.
• In this order, words are written in increasing order of their length,
and words of the same length are written in alphabetical order.
• For example,
Σ = {𝑎 𝑏}
Σ ∗ = {𝜀 𝑎 𝑏 𝑎𝑎 𝑎𝑏 𝑏𝑎 𝑏𝑏 𝑎𝑎𝑎 𝑎𝑎𝑏 … … }

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2022 19

Defining Languages
Defining Languages
• Finite languages
• Can be defined by writing down all words of the language using set notation

• Infinite languages
• Impossible to write down all words of the language
• Must be defined using a set of rules
• Natural languages (such as English) are not suitable for defining complex
languages due to their inherent ambiguity
• Formal notations must be used

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2022 21

Defining Languages (2)
• There are two ways to formally define a language:
• Using grammar (such as Regular Expressions)
• Using automata (or machines)

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2022 22

Grammars
• There are different types of grammars such as:
• Regular Expressions
• Context-free grammars
• Context-sensitive grammars
• Free (or unrestricted) grammars

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2022 23

Machines
• There are different types of machines such as:
• Finite-state automata (FSA)
• Push-down automata (PDA)
• Linear bounded automata (LBA)
• Turing machines (TM)

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2022 24

Regular Expressions
Regular Expressions
• A regular expression consists of:
• Alphabet symbols and 𝜀
• + operator (used as alternation symbol)
• ∗ operator (used to repeat a symbol or subexpression zero or more times)
• ( ) (parentheses – used to group subexpressions)

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2022 26

Regular Expressions – Examples
• Example 1
Σ = {𝑎 𝑏}
𝐿 = {𝜀 𝑎 𝑎𝑎 𝑎𝑎𝑎 𝑎𝑎𝑎𝑎 … … }
𝑅. 𝐸. = 𝑎∗
• Example 2
Σ = {𝑎 𝑏}
𝐿 = {𝑎 𝑎𝑎 𝑎𝑎𝑎 𝑎𝑎𝑎𝑎 … … }
𝑅. 𝐸. = 𝑎𝑎∗

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2022 27

Regular Expressions – Examples
• Example 3
Σ = {𝑎 𝑏}
𝐿 = {𝜀 𝑎𝑏 𝑎𝑏𝑎𝑏 𝑎𝑏𝑎𝑏𝑎𝑏 𝑎𝑏𝑎𝑏𝑎𝑏𝑎𝑏 … … }
𝑅. 𝐸. = (𝑎𝑏)∗
• Example 4
Σ = {𝑎 𝑏}
𝐿 = 𝐾𝑙𝑒𝑒𝑛𝑒 𝑐𝑙𝑜𝑠𝑢𝑟𝑒 𝑙𝑎𝑛𝑔𝑢𝑎𝑔𝑒
𝑅. 𝐸. = (𝑎 + 𝑏)∗

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2022 28

Regular Expressions – Examples
• Example 5
Σ = {𝑎 𝑏}
𝐿 = {𝑎𝑏 𝑎𝑏𝑏 𝑏𝑏𝑎}
𝑅. 𝐸. = 𝑎𝑏 + 𝑎𝑏𝑏 + 𝑏𝑏𝑎
• Example 6
Σ = {𝑎 𝑏}
𝐿 = 𝐿𝑎𝑛𝑔𝑢𝑎𝑔𝑒 𝑜𝑓 𝑎𝑙𝑙 𝑠𝑡𝑟𝑖𝑛𝑔𝑠 𝑤ℎ𝑖𝑐ℎ 𝑏𝑒𝑔𝑖𝑛 𝑤𝑖𝑡ℎ 𝑏
𝑅. 𝐸. = 𝑏(𝑎 + 𝑏)∗

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2022 29

Regular Expressions – Examples
• Example 7
Σ = {𝑎 𝑏}
𝐿 = 𝐿𝑎𝑛𝑔𝑢𝑎𝑔𝑒 𝑜𝑓 𝑎𝑙𝑙 𝑠𝑡𝑟𝑖𝑛𝑔𝑠 ℎ𝑎𝑣𝑖𝑛𝑔 𝑒𝑣𝑒𝑛 𝑙𝑒𝑛𝑔𝑡ℎ
𝑅. 𝐸. = ( 𝑎 + 𝑏 𝑎 + 𝑏 )∗
• Example 8
Σ = {𝑎 𝑏}
𝐿 = 𝐿𝑎𝑛𝑔𝑢𝑎𝑔𝑒 𝑜𝑓 𝑎𝑙𝑙 𝑠𝑡𝑟𝑖𝑛𝑔𝑠 𝑤ℎ𝑖𝑐ℎ 𝑏𝑒𝑔𝑖𝑛 𝑤𝑖𝑡ℎ 𝑎 𝑑𝑜𝑢𝑏𝑙𝑒 𝑙𝑒𝑡𝑡𝑒𝑟
𝑅. 𝐸. = (𝑎𝑎 + 𝑏𝑏)(𝑎 + 𝑏)∗

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2022 30

Regular Expressions – Examples
• Example 9
Σ = {𝑎 𝑏}
𝐿 = 𝐿𝑎𝑛𝑔𝑢𝑎𝑔𝑒 𝑜𝑓 𝑎𝑙𝑙 𝑠𝑡𝑟𝑖𝑛𝑔𝑠 𝑤ℎ𝑖𝑐ℎ 𝑑𝑜 𝑛𝑜𝑡 𝑐𝑜𝑛𝑡𝑎𝑖𝑛 𝑠𝑢𝑏𝑠𝑡𝑟𝑖𝑛𝑔 𝑎𝑏
𝑅. 𝐸. = 𝑏 ∗ 𝑎∗
• Example 10
Σ = {𝑎 𝑏}
𝐿 = 𝐿𝑎𝑛𝑔𝑢𝑎𝑔𝑒 𝑜𝑓 𝑎𝑙𝑙 𝑠𝑡𝑟𝑖𝑛𝑔𝑠 𝑤ℎ𝑖𝑐ℎ 𝑐𝑜𝑛𝑡𝑎𝑖𝑛 𝑎 𝑑𝑜𝑢𝑏𝑙𝑒 𝑙𝑒𝑡𝑡𝑒𝑟
𝑅. 𝐸. = (𝑎 + 𝑏)∗ (𝑎𝑎 + 𝑏𝑏)(𝑎 + 𝑏)∗

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2022 31

Regular Expressions – Examples
• Example 11
Σ = {𝑎 𝑏}
𝐿 = 𝐿𝑎𝑛𝑔𝑢𝑎𝑔𝑒 𝑜𝑓 𝑎𝑙𝑙 𝑠𝑡𝑟𝑖𝑛𝑔𝑠 𝑖𝑛 𝑤ℎ𝑖𝑐ℎ 𝑠𝑒𝑐𝑜𝑛𝑑 𝑠𝑦𝑚𝑏𝑜𝑙 𝑖𝑠 𝑏
𝑅. 𝐸. = 𝑎 + 𝑏 𝑏(𝑎 + 𝑏)∗
• Example 12
Σ = {𝑎 𝑏}
𝐿 = 𝐿𝑎𝑛𝑔𝑢𝑎𝑔𝑒 𝑜𝑓 𝑎𝑙𝑙 𝑠𝑡𝑟𝑖𝑛𝑔𝑠 𝑖𝑛 𝑤ℎ𝑖𝑐ℎ 𝑠𝑒𝑐𝑜𝑛𝑑 𝑠𝑦𝑚𝑏𝑜𝑙 𝑖𝑠 𝑛𝑜𝑡 𝑏
𝑅. 𝐸. = 𝜀 + 𝑎 + 𝑏 + 𝑎 + 𝑏 𝑎(𝑎 + 𝑏)∗

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2022 32

Regular Expressions – Examples
• Example 13
Σ = {𝑎 𝑏}
𝐿 = 𝐿𝑎𝑛𝑔𝑢𝑎𝑔𝑒 𝑜𝑓 𝑎𝑙𝑙 𝑠𝑡𝑟𝑖𝑛𝑔𝑠 𝑤ℎ𝑖𝑐ℎ 𝑐𝑜𝑛𝑡𝑎𝑖𝑛 𝑒𝑥𝑎𝑐𝑡𝑙𝑦 𝑡𝑤𝑜 𝑎′ 𝑠
𝑅. 𝐸. = 𝑏 ∗ 𝑎𝑏 ∗ 𝑎𝑏 ∗
• Example 14
Σ = {𝑎 𝑏}
𝐿 = 𝐿𝑎𝑛𝑔𝑢𝑎𝑔𝑒 𝑜𝑓 𝑎𝑙𝑙 𝑠𝑡𝑟𝑖𝑛𝑔𝑠 𝑤ℎ𝑖𝑐ℎ 𝑐𝑜𝑛𝑡𝑎𝑖𝑛 𝑎𝑡 𝑚𝑜𝑠𝑡 𝑡𝑤𝑜 𝑎′ 𝑠
𝑅. 𝐸. = 𝑏 ∗ (𝜀 + 𝑎)𝑏 ∗ (𝜀 + 𝑎)𝑏 ∗
𝑅. 𝐸. = 𝑏 ∗ + 𝑏 ∗ 𝑎𝑏 ∗ + 𝑏 ∗ 𝑎𝑏 ∗ 𝑎𝑏 ∗
CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2022 33
Regular Expressions – Examples
• Example 15
Σ = {𝑎 𝑏}
𝐿 = 𝐿𝑎𝑛𝑔𝑢𝑎𝑔𝑒 𝑜𝑓 𝑎𝑙𝑙 𝑠𝑡𝑟𝑖𝑛𝑔𝑠 𝑤ℎ𝑖𝑐ℎ 𝑐𝑜𝑛𝑡𝑎𝑖𝑛 𝑎𝑡 𝑙𝑒𝑎𝑠𝑡 𝑡𝑤𝑜 𝑎′ 𝑠
𝑅. 𝐸. = 𝑏 ∗ 𝑎𝑎∗ 𝑏 ∗ 𝑎𝑎∗ 𝑏 ∗ − 𝑖𝑛𝑐𝑜𝑟𝑟𝑒𝑐𝑡, 𝑤ℎ𝑦?
𝑅. 𝐸. = 𝑎 + 𝑏 ∗ 𝑎(𝑎 + 𝑏)∗ 𝑎(𝑎 + 𝑏)∗
𝑅. 𝐸. = 𝑏 ∗ 𝑎(𝑎 + 𝑏)∗ 𝑎(𝑎 + 𝑏)∗
𝑅. 𝐸. = 𝑏 ∗ 𝑎𝑏 ∗ 𝑎(𝑎 + 𝑏)∗

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2022 34

Regular Expressions – Examples
• Example 16
Σ = {𝑎 𝑏}
𝐿 = 𝐿𝑎𝑛𝑔𝑢𝑎𝑔𝑒 𝑜𝑓 𝑎𝑙𝑙 𝑠𝑡𝑟𝑖𝑛𝑔𝑠 𝑤ℎ𝑖𝑐ℎ 𝑑𝑜 𝑛𝑜𝑡 𝑐𝑜𝑛𝑡𝑎𝑖𝑛 𝑡𝑤𝑜 𝑐𝑜𝑛𝑠𝑒𝑐𝑢𝑡𝑖𝑣𝑒 𝑎′ 𝑠
𝑅. 𝐸. = (𝜀 + 𝑎)(𝑏 + 𝑏𝑎)∗

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2022 35

Finite State Automata
Finite State Automata
• A finite-state automaton (FSA) consists of:-
• States
• Transitions

• States are usually numbered as 1,2,3,…… for identification

• Transitions are labelled by alphabet symbols
• There are two types of FSA:-
• Deterministic FSA (called DFA or simply FSA)
• Non-deterministic FSA (called NFA)

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2022 37

Deterministic FSA
• A deterministic FSA has
• A unique START state (or INITIAL state) denoted by an incoming arrow without a
source state
• Zero or more FINAL states denoted by double circles
• Each state must have a unique outgoing transition for each alphabet symbol

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2022 38

Language of an FSA
• We can run a given string on a given FSA such that:-
• Execution starts in the START state
• For each input symbol, we follow the corresponding transition

• At the end of execution, if a final state is reached, the string is said

to be accepted on the FSA
• If at the of execution, a non-final state is reached, the string is said
to be rejected on the FSA
• Thus every string is either accepted or rejected on a given FSA
• Language of an FSA is the set of all those strings which are accepted
on the FSA

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2022 39

FSA – Examples
• Example 1
Σ = {𝑎 𝑏}
𝑊ℎ𝑎𝑡 𝑖𝑠 𝑡ℎ𝑒 𝑙𝑎𝑛𝑔𝑢𝑎𝑔𝑒 𝑑𝑒𝑓𝑖𝑛𝑒𝑑 𝑏𝑦 𝑡ℎ𝑖𝑠 𝐹𝑆𝐴?

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2022 40

FSA – Examples
Let us run the strings
𝜀, 𝑎, 𝑏, 𝑎𝑎, 𝑎𝑏, 𝑏𝑎, 𝑏𝑏, 𝑎𝑎𝑎, 𝑎𝑎𝑏, 𝑎𝑏𝑎, 𝑎𝑏𝑏, 𝑏𝑎𝑎, 𝑏𝑎𝑏, 𝑏𝑏𝑎, 𝑏𝑏𝑏, … …
𝜀 𝑖𝑠 𝑟𝑒𝑗𝑒𝑐𝑡𝑒𝑑
𝑎 𝑖𝑠 𝑟𝑒𝑗𝑒𝑐𝑡𝑒𝑑
𝑏 𝑖𝑠 𝑟𝑒𝑗𝑒𝑐𝑡𝑒𝑑
𝑎𝑎 𝑖𝑠 𝑟𝑒𝑗𝑒𝑐𝑡𝑒𝑑
𝑎𝑏 𝑖𝑠 𝑎𝑐𝑐𝑒𝑝𝑡𝑒𝑑
𝑏𝑎 𝑖𝑠 𝑟𝑒𝑗𝑒𝑐𝑡𝑒𝑑
𝑏𝑏 𝑖𝑠 𝑎𝑐𝑐𝑒𝑝𝑡𝑒𝑑
𝑎𝑎𝑎 𝑖𝑠 𝑟𝑒𝑗𝑒𝑐𝑡𝑒𝑑
CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2022 41
FSA – Examples
𝑎𝑎𝑏 𝑖𝑠 𝑟𝑒𝑗𝑒𝑐𝑡𝑒𝑑
𝑎𝑏𝑎 𝑖𝑠 𝑎𝑐𝑐𝑒𝑝𝑡𝑒𝑑
𝑎𝑏𝑏 𝑖𝑠 𝑎𝑐𝑐𝑒𝑝𝑡𝑒𝑑
𝑏𝑎𝑎 𝑖𝑠 𝑟𝑒𝑗𝑒𝑐𝑡𝑒𝑑
𝑏𝑎𝑏 𝑖𝑠 𝑟𝑒𝑗𝑒𝑐𝑡𝑒𝑑
𝑏𝑏𝑎 𝑖𝑠 𝑎𝑐𝑐𝑒𝑝𝑡𝑒𝑑
𝑏𝑏𝑏 𝑖𝑠 𝑎𝑐𝑐𝑒𝑝𝑡𝑒𝑑
𝐿 = {𝑎𝑏, 𝑏𝑏, 𝑎𝑏𝑎, 𝑎𝑏𝑏, 𝑏𝑏𝑎, 𝑏𝑏𝑏, … … }
Language of all strings having second symbol 𝑏
CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2022 42
FSA – Examples
• Example 2
Σ = {𝑎 𝑏}
𝐿𝑎𝑛𝑔𝑢𝑎𝑔𝑒 𝑜𝑓 𝑎𝑙𝑙 𝑠𝑡𝑟𝑖𝑛𝑔𝑠 𝑠𝑡𝑎𝑟𝑡𝑖𝑛𝑔 𝑤𝑖𝑡ℎ 𝑎
𝑅. 𝐸. = 𝑎(𝑎 + 𝑏)∗

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2022 43

FSA – Examples
• Example 3
Σ = {𝑎 𝑏}
𝐿𝑎𝑛𝑔𝑢𝑎𝑔𝑒 = 𝐾𝑙𝑒𝑒𝑛𝑒 𝐶𝑙𝑜𝑠𝑢𝑟𝑒
𝑅. 𝐸. = (𝑎 + 𝑏)∗

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2022 44

FSA – Examples
• Example 4
Σ = {𝑎 𝑏}
𝐿𝑎𝑛𝑔𝑢𝑎𝑔𝑒 𝑜𝑓 𝑎𝑙𝑙 𝑡ℎ𝑜𝑠𝑒 𝑠𝑡𝑟𝑖𝑛𝑔𝑠 𝑖𝑛 𝑤ℎ𝑖𝑐ℎ 𝑏 ′ 𝑠 𝑛𝑒𝑣𝑒𝑟 𝑎𝑝𝑝𝑒𝑎𝑟 𝑎𝑓𝑡𝑒𝑟 𝑎′ 𝑠
𝑅. 𝐸. = 𝑏 ∗ 𝑎∗

CS5113 Advanced Theory of Computation – by Dr. Aamer Nadeem Spring 2022 45

Thank you!