KIADB Thimmanahalli, Industrial Area

KANDALI – 573217, Hassan - Karnataka

Affiliated to VTU, Recognized by Govt. of Karnataka, Approved by AICTE

Department of Artificial Intelligence & Machine Learning

Assignment 1: Theory of Computation (BCS503)
5th SEMESTER AY: 2025-2026 (ODD)
Sl. Questions
No.
1. Define the following terms with example:
i) Alphabet ii) Power of an Alphabet iii) Strings iv) Languages

Alphabet (Σ)
An alphabet is a finite, non-empty set of symbols.
These symbols are the basic building blocks used to form strings.
Examples:
Σ = {0, 1} – binary alphabet
Σ = {a, b, c} – alphabet of three letters

Power of an Alphabet (Σ*)

The power of an alphabet, denoted Σ*, is the set of all possible strings
(including the empty string ε) that can be formed by concatenating zero or
more symbols from the alphabet.

∗
Σ ={ w ∣ w is a string of symbols from Σ }
Here ε (the empty string) is always included.
We can also define Σⁿ = set of all strings of length n over Σ.
Example:
If Σ = {a, b}
 Σ⁰ = {ε}
 Σ¹ = {a, b}
 Σ² = {aa, ab, ba, bb}
 Σ* = {ε, a, b, aa, ab, ba, bb, aaa, aab, … } (infinite set)

Language
A language is any set of strings formed from an alphabet (that is, any subset
of Σ*).
Formally:
L⊆Σ*
Examples:
 Over Σ = {0,1},

o L₂ = { w ∈ Σ* | w contains an even number of 0s } – an

o L₁ = {ε, 0, 11} – a finite language.

infinite language.
 Over Σ = {a,b},
o L = { aⁿbⁿ | n ≥ 0 } – all strings with equal number of a’s
followed by b’s.
 KIADB Thimmanahalli, Industrial Area
KANDALI – 573217, Hassan - Karnataka
Affiliated to VTU, Recognized by Govt. of Karnataka, Approved by AICTE

Department of Artificial Intelligence & Machine Learning

String
A string is a finite sequence of symbols taken from a given alphabet Σ.
 Symbols are written one after another (concatenated).
 The length of a string is the number of symbols it contains.
 The empty string, written ε, has length 0.
Examples:
 If Σ = {0, 1}, then 0, 101, and 1100 are strings.
 If Σ = {a, b}, then aab, b, and abba are strings.
 ε is a valid string of length 0 over any alphabet.

Reversal of a String
The reversal of a string w, written as wR, is the string obtained by writing the
symbols of w in the opposite order.
If

where each ai∈Σ,

w=a1a2a3…an

then
wR=anan−1…a2a1.

Empty String: εR=ε.

Double Reversal: (wR)R=w
String w Reversal wR
ε (empty) ε
a a
ab ba
0101 1010
abcde edcba

Concatenation of Languages
Let L1 and L2 be two languages over the same alphabet Σ.
The concatenation of L1 and L2, written
L1⋅L2 or simply L1L2,
is the set of all strings that can be formed by taking any string from L1 and
immediately following it with any string from L2.
Formally:
L1L2={ xy∣x∈L1, y∈L2 }.
 KIADB Thimmanahalli, Industrial Area
KANDALI – 573217, Hassan - Karnataka
Affiliated to VTU, Recognized by Govt. of Karnataka, Approved by AICTE

Department of Artificial Intelligence & Machine Learning

2. Define Deterministic Finite Automata. Explain the two preferred

notations for describing the Transition Function with an example.
A Deterministic Finite Automaton is a mathematical model of computation
used to recognize regular languages.
It is defined as a 5-tuple:
M=(Q, Σ, δ, q0, F)
where
 Q – Finite set of states.
 Σ – Finite input alphabet (symbols).

 q₀ – Start state, q0∈Q.

 δ – Transition function δ:Q×Σ→Q.

 F – Set of accepting (final) states, F⊆Q.

Deterministic means:
For every state q∈Q and every input symbol a∈Σ, exactly one next state
δ(q,a) is defined.

Transition Function (δ)

The transition function tells the automaton which state to move to, given:
 the current state, and
 the current input symbol.
There are two preferred notations for describing δ:
Transition Table
Transition Diagram (State Diagram)
 KIADB Thimmanahalli, Industrial Area
KANDALI – 573217, Hassan - Karnataka
Affiliated to VTU, Recognized by Govt. of Karnataka, Approved by AICTE

Department of Artificial Intelligence & Machine Learning

Transition Table
A tabular form listing current states as rows and input symbols as columns.
Each cell shows the next state.
Example DFA:
 Q = {q0, q1}
 Σ = {0, 1}
 Start state q0
 Accepting state F = {q1}
 Language: set of binary strings ends with 0.
Transition function δ:
The transition table is as follows −
State/input symbol 0 1

->q0 q1 q0

*q1 q1 q0
Transition Diagram
A directed graph where:
 Nodes = states.
 Edges = transitions labeled with input symbols.
 Start state marked with an incoming arrow.
 Accepting states shown as double circles.

3. Draw a DFA to accept the set of all strings that contain a substring aba.

4. Draw a DFA to accept strings of a’s and b’s that contain not more than three
b’s.

5. Draw a DFA to accept the language

 KIADB Thimmanahalli, Industrial Area
KANDALI – 573217, Hassan - Karnataka
Affiliated to VTU, Recognized by Govt. of Karnataka, Approved by AICTE

Department of Artificial Intelligence & Machine Learning

L= {w | w ∈ {a, b}* : No 2 consecutive characters are same in w.

6. Design a DFA to accept each of the following languages:

L= { w ϵ {0, 1}* : w has 001 as a substring }

7. Design DFA for the given language.

L= { w ϵ {0, 1}* : w does not end in 01}

8. Design DFA for the given language.

L= { w ϵ {a, b}* : every a in w is immediately preceded and followed by b }

9. Design DFA to Accept stings of 0’s and 1’s L={ starting with 01 or
starting with 10}
 KIADB Thimmanahalli, Industrial Area
KANDALI – 573217, Hassan - Karnataka
Affiliated to VTU, Recognized by Govt. of Karnataka, Approved by AICTE

Department of Artificial Intelligence & Machine Learning

10. Design DFA to accept strings of a’s and b’s where language L={|W|
mod5=|W|mod4}

11. Construct a DFA to accept strings of 0’s and 1’s starting with at least two
0’s and ending with at least two 1’s.

12. Construct the DFA for the given language:

L= { w | w ϵ {a, b}* : w does not contain the substring aab }

13. Construct the DFA for the following languages:

L= { w | w ϵ {a, b}* : where w ends either with ab or ba }

14. Construct DFA for the language,

L= { w | w ϵ {a, b} * :where w is having even number of a’s and odd
number of b’s.}
 KIADB Thimmanahalli, Industrial Area
KANDALI – 573217, Hassan - Karnataka
Affiliated to VTU, Recognized by Govt. of Karnataka, Approved by AICTE

Department of Artificial Intelligence & Machine Learning

15. Obtain a DFA to accept strings of a’s and b’s having odd number of a’s
and even number of b’s.

16. Design DFA

To accept strings having even number of a’s and even number of b’s.

17. Design a DFA to accept each of the following languages:

L= { w ϵ {a, b}* : w has even number of a’s and even number of b’s.

18. Design DFA to accept strings having odd number of a’s and odd number of
b’s
 KIADB Thimmanahalli, Industrial Area
KANDALI – 573217, Hassan - Karnataka
Affiliated to VTU, Recognized by Govt. of Karnataka, Approved by AICTE

Department of Artificial Intelligence & Machine Learning

19. Draw a DFA to accept decimal strings divisible by 3.

L={ w ∈ {0, 1}* : w is a string divisible by 5}.

20. Design a DFA for the Language:

21. Design DFA to accept strings over {a, b} such that each block of 5 (length
five) consecutive symbols have at least two a’s.

22. Design DFA to accept strings having number of a’s divisible by 5 and
number of b’s divisible by 3.
 KIADB Thimmanahalli, Industrial Area
KANDALI – 573217, Hassan - Karnataka
Affiliated to VTU, Recognized by Govt. of Karnataka, Approved by AICTE

Department of Artificial Intelligence & Machine Learning

23. Design DFA to accept binary numbers divisible by 5.

24. Design DFA to accept L= { w (ab + ba) | w ϵ {a, b}* }

25. Design DFA to accept L= { w bab | w ϵ {a, b}* }

26. Define NFA. Convert the following NFA to its equivalent DFA.

27. Obtain NFA which accepts strings of a’s and b’s starting with the string
 KIADB Thimmanahalli, Industrial Area
KANDALI – 573217, Hassan - Karnataka
Affiliated to VTU, Recognized by Govt. of Karnataka, Approved by AICTE

Department of Artificial Intelligence & Machine Learning

ab

28. Convert the NFA in the given fig. to its equivalent DFA.

29. Convert the following NFA to its equivalent DFA.

30. Define NFA. Convert the following NFA to its equivalent DFA. (Or
Obtain a DFA for the following NFA using lazy evaluation method.)
 KIADB Thimmanahalli, Industrial Area
KANDALI – 573217, Hassan - Karnataka
Affiliated to VTU, Recognized by Govt. of Karnataka, Approved by AICTE

Department of Artificial Intelligence & Machine Learning

31. Convert the following NFA given in fig. below to its equivalent DFA.

32. Convert the following NFA given in fig. below to its equivalent DFA.
 KIADB Thimmanahalli, Industrial Area
KANDALI – 573217, Hassan - Karnataka
Affiliated to VTU, Recognized by Govt. of Karnataka, Approved by AICTE

Department of Artificial Intelligence & Machine Learning

33. Obtain NFA for the Regular Expression (a+b)*aa(a+b)*

34. Define Regular Expression. Write RE for the following Languages.

Strings of 0’s and 1’s ending with three consecutive zeros.
Strings of a’s and b’s having substring aa.

35. Write regular expression for the following language

L= { 0n1m | m ≥1, n ≥ 1, mn ≥ 3
L= { w ϵ {a, b}* : w has at most one pair of consecutive a’s }

36. Define Regular Expressions.

 KIADB Thimmanahalli, Industrial Area
KANDALI – 573217, Hassan - Karnataka
Affiliated to VTU, Recognized by Govt. of Karnataka, Approved by AICTE

Department of Artificial Intelligence & Machine Learning

37. Obtain RE to accept strings of a’s and b’s whose second symbol from
the right end is a.
RE= (a + b)* a (a + b)
38. Obtain RE to accept words with two or more letters but beginning and
ending with the same letter where {a, b} are inputs.
a (a + b)*a + b (a + b)*b
39. Write the regular expression for the following languages:
L={ a2nb2m | n ≥ 0, m ≥ 0 }
L= { an bm | m ≥ 1, n ≥ 1, n+m ≥ 3}
L= {w | w ϵ {a, b}* and |w| is multiples of 3}

40. Define NFA. Obtain an ϵ- NFA which accept strings consisting of 0 or more
a’s, followed by 0 or more b’s, followed by 0 or more c’s. Also convert it to

41. Obtain an ∈-NFA for the Regular Expression (a+b)* bb (a+b)*

DFA.

42. List applications of RE. What are the notations used in UNIX Operation
system? List few Regular expressions with its UNIX notations.
43. Develop Regular expressions for the following Languages on Ʃ = { a, b}
i) Accept strings of a’s and b’s whose fifth symbol from the right end is a.
ii) Accept strings of a’s and b’s containing not more than 3 a’s.
44. Find Regular language accepted by the following FA by eliminating states?

45. Find E-Closure of all the states

Convert following NFA to DFA
 KIADB Thimmanahalli, Industrial Area
KANDALI – 573217, Hassan - Karnataka
Affiliated to VTU, Recognized by Govt. of Karnataka, Approved by AICTE

Department of Artificial Intelligence & Machine Learning

46. Obtain a regular expression for the following:

L = {anbm | n ≥ 4, m<=3}
L= {w: na(w) mod 3 = 0 where w ϵ (a, b)*}
L= {w: strings ends with ab or ba where w ϵ (a, b)*}
L = {a2nb2m | n ≥ 0, m ≥ 0}

47. Write regular expression for the following language:

L = {a2nb2m | n ≥ 0, m ≥ 0}
L = {an bm | m ≥ 1, n ≥ 1, nm ≥ 3}

48.
Obtain the Regular Expression for the following Finite
Automaton
 KIADB Thimmanahalli, Industrial Area
KANDALI – 573217, Hassan - Karnataka
Affiliated to VTU, Recognized by Govt. of Karnataka, Approved by AICTE

Department of Artificial Intelligence & Machine Learning

49. Obtain a Regular expression for the following Finite Automaton.

50. Draw a FSM (ϵ - NFA) for the given below regular expressions:
(0+1)* 0 (0+1)* 0
ab (a+b)* a

51. Construct a Regular Expression from the following DFA using state
elimination method.