DEPARTMENT OF COMPUTER SCIENCE & BUSINESS SYSTEMS, CANARA ENGINEERING COLLEGE

Programme:B.E. CIE: ASSIGNMENT –1 Semester: V

Course Title: Theory of Computation Course Code: BCS503

Date: 25/09/2024 Submission: 30/10/2024 Section: A

Group Question
Question
No No
1 Construct DFA for the following
G1  starts with abb
 Ends with bab
Implement the same in JFLAP and verify.
2 Minimize the DFA.

Implement the same in JFLAP and verify.

3 Construct the Finite Automata from the following Regular Expression:
▪ (a U b)* aa (b U aa) bb
▪ (aba ∪aabaa)*
Implement the same in JFLAP and verify.
1 Construct DFA:
G2 {w ∈ {a, b, c}* : between any two a’s there is an odd number of b’s}
Implement the same in JFLAP and verify.
2 Convert NFA to DFA.

Implement the same in JFLAP and verify.

3 Construct DFA for the following:
▪ (ab)*(aab)
▪ (ba U ((a U bb) a*b))
Implement the same in JFLAP and verify.
1 Construct DFA to recognize strings where no. of a’s divisible by 3 <=no. of b’s divisible
G3 by 2. Implement the same in JFLAP and verify.
2 Construct Minimum State Automaton equivalent to the DFA given table. Implement the
same in JFLAP and verify.
3 Simplify the following Regular Expression
 a ( (a ∪ b)(b ∪ a) )* ∪ a ( (a ∪ b) a )* ∪ a
 (a ∪ b)*a* ∪ b
Implement the same in JFLAP and verify.
1 Construct DFSM L = {w ℇ {a,b}* : w has both aa&bb as a substrings}
G4 2 Apply NFA to DFA.

Implement the same in JFLAP and verify.

3 Give English description of the languages of the following Regula Expression:
a)(1+Ɛ)(00*1)*0*
b)(0*1*)*000(0+1)*
Implement the same in JFLAP and verify.
1 Construct DFA:
G5 L = {w ℇ {a,b }*: w has neither ab nor bb as a substring}
Implement the same in JFLAP and verify.
2 Construct DFA:
The set of binary strings with at most one pair of consecutive 0’s and at most one pair of
consecutive 1’s.
Implement the same in JFLAP and verify.
3 Use to show a regular expression that describes L(M)

Implement the same in JFLAP and verify.

1 Draw a DFA to accept decimal string divisible by 3&5.
G6 Implement the same in JFLAP and verify.
2 L = {w ℇ {0-9}* : w corresponds to the decimal encoding, without leading 0's, of an odd
natural number}
Implement the same in JFLAP and verify.
3 Write Regular expressions for the following language:
a) Set of all string’s of 0’s and 1’s not containing 101 as substring
b) Set of all string’s of 0’s and 1’s whose number of 0’s divisible by five and whose
number of 1’s is even
Implement the same in JFLAP and verify.
1 Draw a DFA to accept binary string divisible by 2&5. Implement the same in JFLAP and
verify.
G7 2 Construct DFA:
L = {w ℇ {a,b}* : every a in w is immediately preceded and followed by b}. Implement
the same in JFLAP and verify.
3 Consider the grammar:
S->A1B
A->0A|€
Implement the same in JFLAP and verify.
B->0B|1B|€
Show that this grammar is ambiguous using:
a. Parse Tree
b. Leftmost Derivation
c. Rightmost Derivation
Implement the same in JFLAP and verify.
1 Construct a DFSM L={w ∈ {a, b}* : w does not end in ba}. Implement the same in JFLAP
and verify.
G8 2 Define distinguishable and indistinguishable states. Minimize the following DFA.
Implement the same in JFLAP and verify.

3 Consider the grammar S->aS|aSbS|€

Prove This grammar is ambiguous or not. Show in particular using:
a) Parse tree
b) Leftmost derivation
c) Rightmost derivation
Implement the same in JFLAP and verify.
1 Convert the following ∈-NFA to DFA.
G9

Implement the same in JFLAP and verify.

2 Obtain a DFA accept strings of 0's or 1' s starting with at least two 0’s and ending with
at least two 1’s . Implement the same in JFLAP and verify.
3 Show that for Every DFA There is an Equivalent Regular Expression. Implement the same
in JFLAP and verify.
1 Draw a DFA
G10 L={w ∈ {0, 1}* : w corresponds to the binary encoding, without leading 0’s, of natural
numbers that are evenly divisible by 4}. Implement the same in JFLAP and verify.
2 Apply NFA to DFA algorithm.

Implement the same in JFLAP and verify.

3 L = {w Ꜫ {a,b}* : no two consecutive letters are the same}
1. Construct Regular Expression
2. construt Finite Automata from R.E algorithm to the above language.
Implement the same in JFLAP and verify.
1 Construct DFA where L = {w Ꜫ anbam : n, m ≥ 0}. Implement the same in JFLAP and
G11 verify.
2 Apply NDFA to DFA algorithm; Where Language is string of a’s and b’s

Implement the same in JFLAP and verify.

3 Construct Regular Expression for the following
L = {IP address}
L={C Variables}
Implement the same in JFLAP and verify.
1 Construct DFA:
G12 L = {w Ꜫ {0,1}* : w contains both 101 and 010 as substrings}
Implement the same in JFLAP and verify.
2 Minimize DFA

Implement the same in JFLAP and verify.

3 Develop a DFA to accept the language defined by the following regular expressions
1. (ab)*(aab)*bb
2. (a+ab)*ab*
Implement the same in JFLAP and verify.
1 Construct DFA: W does not have aabc as a substring.
G13 Implement the same in JFLAP and verify.
2 Apply NFA to DFA algorithm.

Implement the same in JFLAP and verify.

3 Construct an DFA for the regular expression
I. 10 + (0 + 11)00*1
II. (((a + ba) b + aa)*
Implement the same in JFLAP and verify.
1 Construct DFA
G14 L={w ∈ {a, b}* : w contains at least one occurrence of the string aababa}. Implement the
same in JFLAP and verify.
2 Use minDFA to minimize M.

Implement the same in JFLAP and verify.

3 Write a RE
 L = {w Ꜫ {a,b}* : w contains an odd number of a’s}
 L={ anbm|n≥1,m≥1,nm≥3}. Implement the same in JFLAP and verify.
1 Convert NFA to DFA algorithm. Implement the same in JFLAP and verify.
G15

2 Construct a DFA for the set of strings that either begin or end (or both) with 01.
Implement the same in JFLAP and verify.
3 Define R.E for the following. Implement the same in JFLAP and verify.
I. L={anbm| n+m is even}
II. L= {w Ꜫ {a,b}* : there is no more than one b}
1 Minimize the following DFA. Implement the same in JFLAP and verify.
G16

2 Write NFA for (0+1)*001(0+1)*. Implement the same in JFLAP and verify.
3 Design a DFA for the set of all strings such that each block of five consecutive symbols
contain at least 2 0’s . Implement the same in JFLAP and verify.
1 Write R.E for the following
G17 L={w€{0,1}*: w has no pair of consecutive zeros}
L ={ w€{a,b,c}*: is a set of all strings which contain atleast one occurrence of each
symbol }. Implement the same in JFLAP and verify.
2 Construct DFA: L={w€{a,b}* :na mod 3 >na mod 2}. Implement the same in JFLAP and
verify.
3 Write a R.E from the DFA using state elimination method. Implement the same in JFLAP
and verify.

1 Construct DFA na mod 3 <na mod 2. Implement the same in JFLAP and verify.
G18 2 Develop a Finite Automata to accept the language defined by each of the following
regular expressions
(aba U aabaa)* . Implement the same in JFLAP and verify.
3 State and prove the Pumping Lemma theorem for Regular Languages. &
Prove L={ap|p is prime} is not regular
1 Construct DFA for the following:
L = {w Ꜫ {0,1}* : every 0 in w is immediately followed by the string 11}. Implement the
G19 same in JFLAP and verify.
2 Define distinguishable and indistinguishable states. Apply DFA algorithm. Implement the
same in JFLAP and verify.
δ 0 1
->A B E
B C F
*C D H
D E H
E F I
*F G B
G H B
H I C
*I A E
3 Write a R.E from the DFA. Implement the same in JFLAP and verify.

1 Build DFAs for the following language

G20 L = {w ℇ {a, b}* : every ‘a’ is immediately followed by a ‘bb’} Implement the same in
JFLAP and verify.
2 Minimize DFA. Implement the same in JFLAP and verify.
δ 0 1
->A B A
B A C
C D B
*D D A
E D F
F G E
G F G
H G D
3 Apply Pumping Lemma Theorem to show that the following languages are not regular.
L = {anb2n: n ≥ 0}
L = {w Ꜫ {),(}* : the parentheses are balanced}. Implement the same in JFLAP and
verify.
1 Prove that following language is not Regular:
i. {0n11n: n>=1}

2 Convert NFA into DFA using subset construction. Implement the same in JFLAP and
verify.
G21 0 1
 p {q,s} {q}
*q {r} {q,r}
r {s} {p}
*s ∅ {p}
3 Prove that L={a : n=2 for some k>=0 } is not regular
n k

G22 1 Prove that following language is not Regular:

i.{0n112n: n>=1}
2 Write NFA for (a+b)*aab(a+b)*. Implement the same in JFLAP and verify.
3 Define a Regular expression for the language. Implement the same in JFLAP and verify.
i. L={w| w Ꜫ {0,1}* and w has no pair of consecutive zeros}
ii. L={anbm: (m+n) is even
G23 1

Implement the same in JFLAP and verify.

2

Implement the same in JFLAP and verify.

3 Construct an equivalent FA for the given regular expression (0+1)*(00+11)(0+1)*
Implement the same in JFLAP and verify.
G24 1 Give a English description for the following:
i. Languages over the alphabet {0,1} is described by the regular expression:
(0+1)*0(0+1)*0(0+1)*
ii. (0*1*)*000(0+1)*
Implement the same in JFLAP and verify.
2 Construct DFA na mod 3 >=na mod 2. Implement the same in JFLAP and verify.
3 Prove that L={0n:n=2k for some k>=0 } is not regular
G25 1 Construct a DFA for the set of strings that either begin or end (or both) with 01.
Implement the same in JFLAP and verify.
2 Define distinguishable and indistinguishable states. Minimize DFA. Implement the same
in JFLAP and verify.
Minimize DFA
δ 0 1
->A B A
B A C
C D B
*D D A
E D F
F G E
G F G
H G D
3 Construct DFA for the following
 Starts with abbaab
 Ends with babaaa
Implement the same in JFLAP and verify.
G26 1 Convert NFA into DFA using subset construction: Implement the same in JFLAP and
verify.
0 1
 p {q} ∅
*q {p} {q,r}
r ∅ {q}

2 Build DFAs for the following language

L = {w ℇ {0, 1}* : every ‘0’ is immediately followed by a ‘11’}
Implement the same in JFLAP and verify.
3 Design a DFA for the set of all strings such that each block of five consecutive symbols
contain at least 2 1’s . Implement the same in JFLAP and verify.
G27 1 Obtain a DFA to accept the language L = { wabb | w € (a,b)* }
Implement the same in JFLAP and verify.
2 Design a DFA for L = {w €{a. b}* : no two consecutive characters are the same}.
Implement the same in JFLAP and verify.
3 Obtain the regular expression for the following finite automata. Implement the same in
JFLAP and verify.

G28 1 Obtain a DFA to accept the language L = { waabw | w € ( a, b)* }. Implement the same in
JFLAP and verify.
2 {w € {a, b}*: w does not end in ba }. Implement the same in JFLAP and verify.
3 Obtain the regular expression for the following finite automata. Implement the same in
JFLAP and verify.

G29 1 Obtain a DFA to accept the language L contains strings of a’s and b’s starting with ab.
Implement the same in JFLAP and verify.
2 {w € {a, b}*: w has both aa and bb as a substring } Implement the same in JFLAP and
verify.
3 Show that L= {ai bj | i ≠ j} is not regular
G30 1 Draw a DFA to accept strings of a’s and b’s such that L = { awa | w € (a+b)* }
Implement the same in JFLAP and verify.
2 w € {0, 1}*: w has no more than one pair of 0’s and no more than one pair of
consecutive l's
Implement the same in JFLAP and verify.
3 Obtain the regular expression for the following finite automata. Implement the same in
JFLAP and verify.

G31 1 Draw a DFA to accept strings of a’s and b’s ending with ab or ba. Implement the same in
JFLAP and verify.
2 Convert the following ε-NFA to DFA. Implement the same in JFLAP and verify.
3 Consider the following DFA - M: Show a regular expression for L(M). Implement the
same in JFLAP and verify.

Students Groups:
4CB22CB001 =>4CB22CB002 G1
4CB22CB003 =>4CB22CB004 G2
4CB22CB005 =>4CB22CB006 G3
4CB22CB007 =>4CB22CB008 G4
4CB22CB009 =>4CB22CB010 G5
4CB22CB011 =>4CB22CB012 G6
4CB22CB013 =>4CB22CB014 G7
4CB22CB015 =>4CB22CB016 G8
4CB22CB017 =>4CB22CB018 G9
4CB22CB019 =>4CB22CB020 G10
4CB22CB021 =>4CB22CB022 G11
4CB22CB023 =>4CB22CB024 G12
4CB22CB025 =>4CB22CB026 G13
4CB22CB027 =>4CB22CB028 G14
4CB22CB029 =>4CB22CB030 G15
4CB22CB031 =>4CB22CB032 G16
4CB22CB033 =>4CB22CB034 G17
4CB22CB035 =>4CB22CB036 G18
4CB22CB037=>4CB22CB038 G19
4CB22CB039=>4CB22CB040 G20
4CB22CB041=>4CB22CB042 G21
4CB22CB043 =>4CB22CB044 G22
4CB22CB045 =>4CB22CB046 G23
4CB22CB047 =>4CB22CB048 G24
4CB22CB049 =>4CB22CB050 G25
4CB22CB051 =>4CB22CB052 G26
4CB22CB053 =>4CB22CB054 G27
4CB22CB055 =>4CB22CB056 G28
4CB22CB057 =>4CB22CB058 G29
4CB22CB059 =>4CB22CB060 G30
4CB22CB061 =>4CB22CB062 G31
Rubrics for Assessment:
SI.No. Criteria for Evaluation Marks
1 Punctuality in submission 2
2 Structure and format 2
3 Orderliness/clarity, readability 2
4 Relevance, correctness of answers 2
5 Academic Honesty 2

Instructions to Students:
1. Assignments should only be written in the assignment book. Screenshots of JFLAP Simulation must
be pasted.
2. Assignment should be submitted on or before the submission date as mentioned above.
3. Use black pen only.
4. Student should answer the assigned questions to their respective USN only.

Signature of Course Instructor with Date Signature of Course Coordinator with Date

APPROVED

Signature of Senior Faculty/Expert with Date Signature of Senior Faculty/Expert with Date

HEAD OF THE DEPARTMENT/CHAIRMAN – MODERATION COMMITTEE