lOMoARcPSD|32221204
Set C - pyq
Formal Language And Automata (SRM Institute of Science and Technology)
Studocu is not sponsored or endorsed by any college or university
Downloaded by Yadav (yadvji568@gmail.com)
lOMoARcPSD|32221204
Register number _____________________________
SRM Institute of Science and Technology
College of Engineering and Technology
School of Computing
SRM Nagar, Kattankulathur – 603203, Chengalpattu District, Tamil Nadu
Academic Year: 2022-23 (ODD)
B.Tech-Computer Science & Engineering
Test: CLA-T3 Date: 23.12.2022
Course Code & Title: 18CSC301T & Formal Languages and Automata
Duration: 2 periods
Year & Sem: III Year /V Sem Max. Marks: 50
Set -C
Course articulation matrix:
PO PO PO PSO PSO PSO
PO 1 PO 2 PO 3 PO 4 PO 5 PO 6 PO 7 PO 8 PO 9
10 11 12 1 2 3
CO-1 3 3
CO-2 3 2 3
CO-3 3 3 3
CO-4 3 3 3
CO-5 3 1 2 3
Part - A
Instructions: Answer any two questions
Q. Question Mark B C P PI
N s L O O Cod
o e
1 Jay vists a store to buy some gallon of milk and bread. First she buys 3 4 4 4.2.1
milk followed by bread, which is twice the quantity of milk.
a) Turing Machine (TM) tape head can move in left, right, up or
down direction in
i. Multi-tape TM
ii. Multi-head TM
iii. Multi-track TM
iv. Multi-dimensional TM
b) A: The Machine Halts when there is no possible transition to
follow
B: The TM final state has an outgoing transition
Which of the following is true ?
i. A and B are true
ii. A and B are false
iii. A is true and B is false
iv. A is false and B is true
3
c) Generate the accepting language L for the given scenario 8
d) Design a TM by mentioning the transition rules for the generated
language. 5
e) Draw a transition diagram and Transition table of the constructed
Downloaded by Yadav (yadvji568@gmail.com)
lOMoARcPSD|32221204
Register number _____________________________
TM 3
4
f) Is it a Computing device or an acceptor. Justify the answer
g) Simulate a TM for MilkMilkBreadBreadBread.
2 An UPI based online payment application wishes to attract new 3 4,5 4 4.2.1
customers. In this perspective, it has decided to give a reward of Rs
5 for every transaction made to the sender as well as the receiver of
the amount.
a) The Turing machines are brain child of __________
i) Programming languages
ii) Microprocessors
iii) Stored program concept
iv) Microcontrollers
b) If MPCP can be solved then PCP can also be solved. Which
property illustrates this?
i) Computational complexity
ii) Decidability
iii) Reducibility
iv) Computability
c) Construct a TM transition rules that calculates the total 8
amount of the receiver (including reward).
d) Draw the transition diagram and table for the same 5
e) Compute the total amount at the receiver if the actual 4
transaction is Rs 6. Illustrate it using instantaneous
description
f) Encode the constructed TM in binary language and then
6
decode them. (6 marks)
3 Every year a common festival is celebrated between two villages A 4 5 4 4.2.1
and B. On an account of this, a local sport is organized by the
villagers. The selection of players in this year happens according to
the given table (Here 0 indicates women and 1 indicates men). The
positioning of the players is made in such a way that at any
particular position, if village A places a set of players from set i,
then village B should also place the set of players from set i only.
This pattern will repeat for other sets also.
i A B
1 11 1011
0
2 11 000
1
3 00 0101
Downloaded by Yadav (yadvji568@gmail.com)
lOMoARcPSD|32221204
Register number _____________________________
1
4 01 0
0
a) Consider the statements:
S1: All recursively enumerable languages are countable.
S2:Set of all non-regular languages over the alphabet {a,b,c}
is recursively enumerable.
i) Both are true
ii) Only S1 is true
iii) Only S2 is true
iv) Both are false
b) A NP complete problem is the conjunction of_________
i) NP hard and NP
ii) NP and P
iii) NP hard and P 10
iv) NP hard alone
c) An audience claims that there are atleast two ways in which
the men and women of villages A and B can be placed after
fulfilling the condition of the game. Is this true? If yes, give 4
the sequence.
d) Assuming the above given table is a MPCP problem, convert 6
it into PCP.
e) Construct a TM, for another game in which if village A
places men then village B should place woman and vice 3
versa. Design a TM to help village B in doing so.
f) Find the arrangement of village B if the village A places
players in the following order: “men, women, women, men”.
CO Blooms
45
Taxonomy
40
L4,33%
35
30
25 L3,67%
20
15
10
0
CO4 CO5
Downloaded by Yadav (yadvji568@gmail.com)
lOMoARcPSD|32221204
Register number _____________________________
Downloaded by Yadav (yadvji568@gmail.com)
lOMoARcPSD|32221204
a) Turing Machine (TM) tape head can move in left, right, up or down direction in
i. Multi-tape TM
ii. Multi-head TM
iii. Multi-track TM
iv. Multi-dimensional TM
b) A: The Machine Halts when there is no possible transition to follow
B: The TM final state has an outgoing transition
Which of the following is true ?
i. A and B are true
ii. A and B are false
iii. A is true and B is false
iv. A is false and B is true
c) Generate the accepting language L for the given scenario. Jay vists a store to buy some
gallon of milk and bread. First she buys milk followed by bread, which is twice the
quantity of milk. Design a TM for the generated language
d) Draw a transition diagram and Transition table of the constructed TM
e) Is it a Computing device or an acceptor. Justify the answer
Simulate a TM for MilkMilkBreadBreadBread
Downloaded by Yadav (yadvji568@gmail.com)
lOMoARcPSD|32221204
Downloaded by Yadav (yadvji568@gmail.com)
lOMoARcPSD|32221204
An UPI based online payment application wishes to attract new customers. In this
perspective, it has decided to give a reward of Rs 5 for every transaction made to the sender
as well as the receiver of the amount.
a) The Turing machines are brain child of __________
i) Programming languages
ii) Microprocessors
Downloaded by Yadav (yadvji568@gmail.com)
lOMoARcPSD|32221204
iii) Stored program concept
iv) Microcontrollers
b) If MPCP can be solved then PCP can also be solved. Which property illustrates this?
i) Computational complexity
ii) Decidability
iii) Reducibility
iv) Computability
c) Construct a TM transition rules that calculates the total amount of the receiver
(including reward).
Downloaded by Yadav (yadvji568@gmail.com)
lOMoARcPSD|32221204
d) Draw the transition diagram and table for the same
e) Compute the total amount at the receiver if the actual transaction is Rs 6. Illustrate it
using instantaneous description
Downloaded by Yadav (yadvji568@gmail.com)
lOMoARcPSD|32221204
Encode the constructed TM in binary language and then decode them. (6 marks)
Downloaded by Yadav (yadvji568@gmail.com)
lOMoARcPSD|32221204
Every year a common festival is celebrated between two villages A and B. On an account of
this, a local sport is organized by the villagers. The selection of players in this year happens
according to the given table (Here 0 indicates women and 1 indicates men). The positioning
of the players is made in such a way that at any particular position, if village A places a set of
players from set i, then village B should also place the set of players from set I only. This
pattern will repeat for other sets also.
i A B
1 11 10110
2 111 000
3 001 0101
4 010 0
Downloaded by Yadav (yadvji568@gmail.com)
lOMoARcPSD|32221204
a) Consider the statements:
S1: All recursively enumerable languages are countable.
S2:Set of all non-regular languages over the alphabet {a,b,c} is recursively
enumerable.
i) Both are true
ii) Only S1 is true
iii) Only S2 is true
iv) Both are false
b) A NP complete problem is the conjunction of_________
i) NP hard and NP
ii) NP and P
iii) NP hard and P
iv) NP hard alone
c) An audience claims that there are atleast two ways in which the men and women of
villages A and B can be placed after fulfilling the condition of the game. Is this true?
If yes, give the sequence.
d) Assuming the above given table is a MPCP problem, convert it into PCP.
e) Construct a TM, for another game in which if village A places men then village B
should place woman and vice versa. Design a TM to help village B in doing so.
Find the arrangement of village B if the village A places players in the following order:
“men, women, women, men”.
Downloaded by Yadav (yadvji568@gmail.com)
