DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
FIFTH SEMESTER B.TECH (2021-’25 BATCH)
CST301 FORMAL LANGUAGES & AUTOMATA THEORY
MODULE 5
QUESTION BANK
Part A - 3-mark questions
Part B - 14-mark questions
Questio Question Mark Bloom’s CO
n No Taxonom
y level
1A.Design TM for L = {anbmbn / m, n > 0}. Illustrate the working with 7 L3 CO4
suitable example
7
1B.Explain Chomsky hierarchy for formal languages and evaluate various 7
types CO1
2A.Explain general notations for productions of each formal language from 7 L2 CO1
Chomsky hierarchy.
2B. Write a context sensitive grammar for the language 𝐿 = {𝑎𝑛 𝑏𝑛 𝑐𝑛 |𝑛 ≥ 7
0}. Also illustrate how the the string 𝑎2𝑏2𝑐2 can be derived from the start
symbol of the proposed grammar
3A.Design a Turing machine to obtain the sum of two natural numbers 𝑎 and 7 L3 CO4
𝑏, both represented in unary on the alphabet set {1}. Assume that initially
the tape contains ⊢ 1𝑎 01𝑏♭𝜔
𝑎+.𝑏The Turing Machine should halt with 1
♭𝜔 as the tape content. Also, illustrate the computation of your Turing
Machine on the input 𝑎 = 3 and 𝑏 = 2.
3B.Design a Turing machine to identify the strings belong to the language 7
L={0n1n| n>0}.
1A.Create a Turing machine that recognizes strings with an equal
count of 0s and 1s. 7 L3 CO4
1B.Explain Chomsky hierarchy and corresponding type0, type1, type2 and 7
type 3 formalism.
8
L1 CO1
2A. Write the Chomsky hierarchy of languages. Prepare a table indicating 7 L2 CO1
the
automata and grammars for the languages in the Chomsky Hierarchy.
2B.Prove that TM halting problem is undecidable. 7 L3 CO4
3A.Design a Turing machine that determines whether the binary input string 7 L3 CO4
is of odd parity or not
3B.How does the Universal Turing machine simulate other Turing machines? 7
9 1A.Show that normal single tape Turing machine can perform computations 7 L2 CO4
performed by a multi-tape Turing machine (informal explanation is
sufficient).
1B.What is a non-deterministic Turing machine?Give an example. 7
2A.Explain why Halting problem is unsolvable problem. 7 L2 CO4
2B.Design a TM to copy a string of a's and b's to the right side, leaving one 7
blank symbol (b) in between. Assume that initially the input tape contains
bxb and TM halts with bxbxb as the tape content. x € {a, b}* .
3A.Design Turing machine to compute addition of two numbers. Assume 7 L3 CO4
unary notation for number representation.Illustrate the model with an
example.
3B.Construct a Turing machine that computes 2’s complement of a binary 7
number.Illustrate the example with a suitable example.
1A.Design Linear Bounded Automata for the language L = { anbn cn| n>=1 }. 7 L3 CO1
10
1B.Design a Turing Machine for the language L = { anb2n | n>=1 }. Illustrate 7
the computation of TM on the input ‘aaabbbbbb’.
CO4
2A.Are there any languages which are not recursively enumerable, but 7 L3 CO1
accepted by a multi-tape Turing machine? Justify your answer.
2B.Design Turing machine to compute addition of two numbers.
Assume unary notation for number representation. Describe all 7
instantaneous descriptions (ID) from initial ID: q0010 to Final ID: 00 CO4
with respect to constructed Turing Machine.(assume q0 as initial
state).
3A.Design a TM to compute the 2’s complement of a binary string and 7 L3 CO4
illustrate the working with an example.
3B.Design a Turing machine to compute the function f(x)=2x. Write the ID
for the input x=2. 7
1A.Design the Turing machine to recognize the language: {0n 1 n 0 n |
n >=1}. Describe all instantaneous descriptions (ID) from initial ID: 7 L3 CO4
q0001100 to Final ID with respect to constructed Turing Machine.
11 (assume q0 as initial state.)
1B.Design Turing machine that accepts all the binary strings whose decimal 7
value is divisible by 3.
2A. Design Turing machine that accepts all the binary strings whose
decimal value is divisible by 4. 7 L3 CO4
2B.Design the Turing machine to recognize the language: {anbnan| n 7
>=1}.Describe all instantaneous descriptions (ID) from initial ID:
q0aabbaa to Final ID with respect to constructed Turing Machine.
(assume q0 as initial state.)
3A. Design a Turing Machine to compute the square of a natural number. 7 L3 CO4
Assume that the input is provided in unary representation.
3B.Design Turing machine that accepts all the binary strings whose decimal
value is divisible by 5. 7
1A.Design a TM to increment a binary number.
7 L3 CO4
1B.Define recursively enumerable languages and explain the concept
of Turing machines recognizing such languages. 7 L2 CO4
2A.Design a TM parity counter that outputs 0 or 1, depending on
12 whether the number of 1s in the input sequence is even or odd 7 L2 CO4
respectively.
2B. Design a TM to find the sum of two numbers m and n. Assume that 7 L3 CO4
initially the tape contains m number of 0s followed by # followed by n
number of 0s.
3A. Design a Turing Machine to implement proper subtraction
function: 14 L3 CO4
f(m,n)={m-n, if m>n : 0 if m<=n} . Write the Instantaneous description
for the conditions m<n and m>n.
