DHANEKULA INSTITUTE OF ENGINEERING & TECHNOLOGY (Approved by AICTE, Affiliated by JNTU, Kakinada) GANGURU::VIJAYAWADA – 521 139
Department of Computer Science & Engineering
: B.Tech in Computer Science &Engineering : Formal Languages & Automata Theory
Name of the program Name of the Course Year &Semester Academic year JNTUK Subject Code Duration
Name of the Faculty
: II -II
: 2021-22 : R20C213 : 70 Min
: Mr. M.Srinivasa Rao
Name of the Exam Subject Code Exam Weightage Date
Set No: I
: Class Test-I : R20C213
: 100%
: 23/03/2022
Course Outcome Number
Course Outcome
Blooms Taxonomy Levels Application (L3)
R20C213.1 Understanding and Constructing DFA, NFA.
----------------------------------------------------------------------------------------------------------- ---
1. a) Explain the following with examples.
(i) String (ii) Empty String (iii) Prefix (iv) Suffix (v) Substring
[R20C213.1, BTL2, Understanding, PO1, 2, 3/PSO 1, 2 --- 5M]
b) Design a DFA which accept all the strings ending with 1010.
[R20C213.1, BTL3, Application, PO1, 2, 3/PSO 1, 2 --- 5M]
2. a) Explain NFA with an example.
[R20C213.1, BTL2, Understanding, PO1, 2, 3/PSO 1, 2 --- 5M]
b) Check whether the following string 1101 is accepted by the following NFA.
[R16C215.1, BTL3, Application, PO1, 2, 3/PSO 1, 2 --- 5M]
01 →q0 q0,q1 q1,q2
q1 q2 - *q2 - -
3. a) Explain briefly about Central Concepts of Automata Theory.
[R20C213.1, BTL2, Understanding, PO1, 2, 3/PSO 1, 2 --- 5M] b) Design NFAs which accept all the strings starting with i) 110 ii) ending with 110
[R20C213.1, BTL3, Application, PO1, 2, 3/PSO 1, 2 --- 5M]
********************************All the Best*********************************
Scheme of Evaluation: 1. a) 5X1=5M 2. a) NFA explanation 3M Example 2M 3. a) Central Concepts 4M Example 1M
b) Transition Diagram 3M, Transition Table 2M b) Acceptance check 5M
b) NFA starting with 3M ending with 2M
DHANEKULA INSTITUTE OF ENGINEERING & TECHNOLOGY (Approved by AICTE, Affiliated by JNTU, Kakinada) GANGURU::VIJAYAWADA – 521 139
Department of Computer Science & Engineering
: B.Tech in Computer Science &Engineering : Formal Languages & Automata Theory
Name of the program Name of the Course Year &Semester Academic year JNTUK Subject Code Duration
Name of the Faculty
: II -II
: 2021-22
: R20C213
: 70 Min Date
: Mr M.Srinivasa Rao
Set No: II
: Class Test-I : R20C213
: 100%
: 23/03/2022
Blooms Taxonomy Levels Application (L3)
Name of the Exam Subject Code Exam Weightage
Course Outcome Number
Course Outcome
R20C213.1 Understanding and Constructing DFA,NFA
----------------------------------------------------------------------------------------------------------- ---
1.
b) Design a DFA which accept all the strings divisible by 7.
a) Explain Finite Automata and Finite State Machines.
[R20C213.1, BTL2,Understanding, PO1,2,3/PSO 1,2 --- 5M] [R20C213.1, BTL3,Application, PO1,2,3/PSO 1,2 --- 5M]
2. a) Explain DFA with an example.
[R20C213.1, BTL2,Understanding, PO1,2,3/PSO 1,2 --- 5M]
b) Check whether the following string 11010 is accepted by the following DFA.
[R20C213.1, BTL3,Application, PO1,2,3/PSO 1,2 --- 5M]
01 →q0 q0 q1 q1 q2 q0 *q2 q0 q1
3. a) Explain NFA with an example.
[R20C213.1, BTL2,Understanding, PO1, 2,3/PSO 1,2 --- 5M] b) Design a NFA which accept all strings starting with 1100 & 0011.
[R20C213.1, BTL3, Application, PO1,2,3/PSO 1,2 --- 5M] ********************************All The Best*********************************
Scheme of Evaluation:
1. a) FA 3M FSM 2M b) Transition Diagram 3M, Transition Table 2M 2. a) DFA explanation 3M Example 2M b) Acceptance check 5M
3. a) NFA explanation 3M Example 2M b) Machine 3M Table 2M
DHANEKULA INSTITUTE OF ENGINEERING & TECHNOLOGY (Approved by AICTE, Affiliated by JNTU, Kakinada) GANGURU::VIJAYAWADA – 521 139
Department of Computer Science Engineering
: B.Tech in Computer Science &Engineering : Formal Languages & Automata Theory
Name of the program Name of the Course Year &Semester Academic year JNTUK Subject Code Duration
Name of the Faculty
: II -II
: 2021-22
: R20C213
: 70 Min Date
: Mr M.Srinivasa Rao
Set No: III
: Class Test-I : R20C213
: 100%
: 23/03/2022
Blooms Taxonomy Levels Application (L3)
Name of the Exam Subject Code Exam Weightage
Course Outcome Number
Course Outcome
R20C213.1 Understanding and Constructing DFA,NFA
1.
2.
----------------------------------------------------------------------------------------------------------- ---
a) Explain about Finite State Machines.
[R20C213.1, BTL2, Understanding, PO1, 2, 3/PSO 1,2 --- 5M]
b) Design a DFA which accept all the strings divisible by 4.
[R20C213.1, BTL3, Application, PO1, 2, 3/PSO 1,2 --- 5M]
a) Design DFA that accepts binary strings containing 1010 as its substring.
[R20C213.1, BTL3, Application, PO1, 2, 3/PSO 1, 2 --- 5M]
b) Check whether the following string 11011 is accepted by the following DFA.
[R20C213.1, BTL3, Application, PO1, 2, 3/PSO 1, 2 --- 5M]
01 →q0 q0 q1 q1 q2 q0 *q2 q0 q1
a) Explain NFA with an example.
[R20C213.1, BTL2, Understanding, PO1, 2, 3/PSO 1, 2 --- 5M] b) Design a NFA which accept all the strings ending with 0101 & 1010.
[R20C213.1, BTL3, Application, PO1, 2, 3/PSO 1, 2 --- 5M]
3.
********************************All The Best********************************* Scheme of Evaluation:
1. a) FSMs Explanation 5M b) Machine 3M, Transition Table 2M
2. a) DFA 3M Table 2M b) Acceptance check 5M
3. a) Machine 3M, Transition Table 2M b) Machine 3M Table 2M
DHANEKULA INSTITUTE OF ENGINEERING & TECHNOLOGY (Approved by AICTE, Affiliated by JNTU, Kakinada) GANGURU::VIJAYAWADA – 521 139
Department of Computer ScienceEngineering
: B.Tech in Computer Science &Engineering : Formal Languages & Automata Theory
Name of the program Name of the Course Year &Semester Academic year JNTUK Subject Code Duration
Name of the Faculty
: II -II
: 2021-22
: R20C213
: 70 Min Date
: Mr M.Srinivasa Rao
Set No: IV
: Class Test-I : R20C213
: 100%
: 23/03/2022
Blooms Taxonomy Levels Application (L3)
Course Outcome Number
Course Outcome
Name of the Exam Subject Code Exam Weightage
R20C213.1 Understanding and Constructing DFA,NFA.
----------------------------------------------------------------------------------------------------------- ---
1. a) Explain about Finite Automata & Finite State Machine
[R20C213.1, BTL2, Understanding, PO1,2,3/PSO 1,2 --- 5M]
b) Design a DFA which accept strings divisible by 6.
[R20C213.1, BTL3, Application, PO1,2,3/PSO 1,2 --- 5M]
2. a) Design DFA that accepts binary strings ending in 001.
[R20C213.1, BTL3, Application, PO1,2,3/PSO 1,2 --- 5M]
b) Check whether the following string 1011 is accepted by the following NFA.
[R20C213.1, BTL3,Application, PO1,2,3/PSO 1,2 --- 5M]
01 →q0 q0,q1 q1,q2
q1 q2 - *q2 - -
3. a) Explain Central Concepts of Automata Theory.
[R20C213.1, BTL2, Understanding, PO1,2,3/PSO 1,2 --- 5M] b) Design a DFA which accept strings whose substring is 000.
[R20C213.1, BTL3, Application, PO1,2,3/PSO 1,2 --- 5M]
********************************All The Best********************************* Scheme of Evaluation:
1. a) FA explanation 5M b) Machine Diagram 3M, Transition Table 2M
2. a) DFA 3M Table 2M b) Acceptance check 5M
3. a) Central Concepts 5M b) Machine 3M Table 2M