KRISHNA ENGINEERING COLLEGE

(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)

Department of Computer Science & Engineering

Session: _______________ Semester: ______________ Section: __________________

Course Code: ____________ Course Name: ___________________________________

Assignment 1

Date of Assignment: 26 April 2022 Date of submission: 2 May 2022

S.N BL, CO Question Marks

Convert it into Mealy machine.

Mohan Nagar, Near Air Force Station- Hindon, Ghaziabad – 201007 (U.P.)
Tel: 0120-2657731, 2657732, TeleFax : 0120-2659513
Email: director@krishnacollege.ac.in, Website : www.krishnacollege.ac.in 1
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)

Department of Computer Science & Engineering

Convert it into Moore machine.

. Draw a deterministic and non-deterministic finite automate which accept 00 and 11 at the end
of a string containing 0, 1 in it, e.g., 01010100 but not 000111010.

. Draw a deterministic and non-deterministic finite automata which accept a string containing
“ing” at the end of a string in a string of {a-z}, e.g., “anything” but not “anywhere”.

Mohan Nagar, Near Air Force Station- Hindon, Ghaziabad – 201007 (U.P.)
Tel: 0120-2657731, 2657732, TeleFax : 0120-2659513
Email: director@krishnacollege.ac.in, Website : www.krishnacollege.ac.in 2
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)

Department of Computer Science & Engineering

Assignment 2

Date of Assignment: 25 may 2022 Date of submission: 30 May 2022

S.No. BL, CO Question Marks

1 Define regular expression? Write regular expression for the languages that 2
have the set of all string of 0’s and 1's beginning with 00.
2 Construct an NFA equivalent to the regular expression 2
((0+1)(00+11)(0+1))*.
3 Prove that regular sets are closed under union and complementation. 2

4 Prove (a+b)*= (a* (ba*))*. 5

5 Prove that - (111*)* = (11 + 111)*. 5

6 Construct a NFA with ɛ-moves for the regular expression (01)*(0+1)*. 5

7 Describe the language denoted by the regular expression (0+ 1)* 1* (0+ 2
1)*.
8 Design a Regular expression that accepts all the strings for input alphabet 2
{a, b} containing exactly 2 a’s.
State recursive definition of regular expression and construct regular 5
expression corresponding to the state transition diagram as shown Fig.l

a) State Pumping Lemma for regular sets. Show that the set L={ap l P 5
10 is a Prime} is not regular.
b) (b) Discuss closure properties i.e. concatenation, union,
intersection, complement of regular languages'

Mohan Nagar, Near Air Force Station- Hindon, Ghaziabad – 201007 (U.P.)
Tel: 0120-2657731, 2657732, TeleFax : 0120-2659513
Email: director@krishnacollege.ac.in, Website : www.krishnacollege.ac.in 3
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)

Department of Computer Science & Engineering

5
12

13 2

Answers:

Mohan Nagar, Near Air Force Station- Hindon, Ghaziabad – 201007 (U.P.)
Tel: 0120-2657731, 2657732, TeleFax : 0120-2659513
Email: director@krishnacollege.ac.in, Website : www.krishnacollege.ac.in 4
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)

Department of Computer Science & Engineering

Assignment 3

Date of Assignment: 8 June 2022 Date of submission: 13 June 2022

Mark
S.No. BL, CO Question
s

1,3 Define Chomsky hierarchy. 2

2
2.

3.

4.

5.

6.

7.

Mohan Nagar, Near Air Force Station- Hindon, Ghaziabad – 201007 (U.P.)
Tel: 0120-2657731, 2657732, TeleFax : 0120-2659513
Email: director@krishnacollege.ac.in, Website : www.krishnacollege.ac.in 5
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)

Department of Computer Science & Engineering

9.

10.

11.

12.

13.

14.

15.

Mohan Nagar, Near Air Force Station- Hindon, Ghaziabad – 201007 (U.P.)
Tel: 0120-2657731, 2657732, TeleFax : 0120-2659513
Email: director@krishnacollege.ac.in, Website : www.krishnacollege.ac.in 6
 KRISHNA ENGINEERING COLLEGE
(Approved by AICTE & Affiliated to Dr. APJ Abdul Kalam Technical University (Formerly UPTU), Lucknow)

Department of Computer Science & Engineering

16.

17.

Mohan Nagar, Near Air Force Station- Hindon, Ghaziabad – 201007 (U.P.)
Tel: 0120-2657731, 2657732, TeleFax : 0120-2659513
Email: director@krishnacollege.ac.in, Website : www.krishnacollege.ac.in 7