Department of Computer and Science Engineering (CSE)
UNIVERSITY INSTITUTE OF
ENGINEERING
COMPUTER SCIENCE
ENGINEERING
Bachelor of Engineering
Theory of Computation (CST-353)
Topic: Introduction DISCOVER . LEARN . EMPOWER
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
Learning Objectives & Outcomes
Objective:
• To understand the concept of Formal Language,
Operations and examples of formal languages.
Outcome:
• Student will understand the
Formal Language
Operation on formal language
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
Languages
L is a said to be a language over alphabet ∑, only if L ∑*
this is because ∑* is the set of all strings (of all possible length
including 0) over the given alphabet ∑
Examples:
1. Let L be the language of all strings consisting of n 0’s followed by n
1’s:
L = {,01,0011,000111,…}
2. Let L be the language of all strings of with equal number of 0’s and
1’s:
L = {,01,10,0011,1100,0101,1010,1001,…}
Definition: Ø denotes the Empty language
• Let L = {}; Is L=Ø? NO
3
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
Language:
A language is a collection of appropriate string. A language
which is formed over Σ can be Finite or Infinite.
Example: 1
• L1 = {Set of string of length 2}
= {aa, bb, ba, bb} Finite Language
Example: 2
• L2 = {Set of all strings starts with 'a'}
= {a, aa, aaa, abb, abbb, ababb} Infinite Language
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
Finite Automata
• Some Applications
– Software for designing and checking the behavior of
digital circuits
– Lexical analyzer of a typical compiler
– Software for scanning large bodies of text (e.g., web
pages) for pattern finding
– Software for verifying systems of all types that have a
finite number of states (e.g., stock market transaction,
communication/network protocol)
5
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
Set operations on languages :
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
Example of Formal Language:
• A language is a collection of appropriate string. A language
which is formed over Σ can be Finite or Infinite.
Example: 1
• L1 = {Set of string of length 2}
= {aa, bb, ba, bb} Finite Language
Example 2 :
• Example of Finite Language: L1 = { set of string of 2 } L1 = { xy,
yx, xx, yy }
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
Example: 3
• L2 = {Set of all strings starts with 'a'}
= {a, aa, aaa, abb, abbb, ababb} Infinite Language
Example 4 :
• Example of Infinite Language: L1 = { set of all strings
starts with 'b' } L1 = { babb, baa, ba, bbb, baab, ....... }
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
Summary
• Operations on Formal language
• Alphabets
• strings
• languages
10
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
FAQ :
1. Construct the powerset for the following sets.
• {a, b}
• {0, 1}∪{1, 2}
• {z}
• {0, 1, 2, 3, 4}∩{1, 3, 5, a}
• {0, 1, 2, 3}−{1, 3, 5, a}
• ∅ (the empty set)
2. Prove that 12 +22+32+……+ n2= ∑n2 =
(n(n+1)(2n+1))/6.
University Institute of Engineering (UIE)
Department of Computer and Science Engineering (CSE)
References :
• Martin J.C., “Introduction to Languages and Theory of
Computation”, Tata McGraw-Hill Publising Company
Limited, 3rd Edition.
• [Link]
• Https://[Link]/wiki/Finite-state_machine
• [Link]
• [Link]
University Institute of Engineering (UIE)
University Institute of Engineering (UIE)