TOC
B.Tech (CSE and CSE-AI&ML)
Assignment
o Instruction:
➢ Please submit in handwritten forms
➢ You can submit it from 20th November 2023 onwards but Last
date of Submission is 24 November 2023
➢ Submission after last date is not allowed in any case
Unit-I
1. Define basic terminologies used in Theory of Computation such as Symbol, Alphabet,
String, Language and power of Σ.
2. Construct a minimal DFA over Σ={a,b}and ω∈(a,b)* such that na(ω)mod2=0 and
nb(ω)mod2=1.
3. Construct NFA for set of all strings over Σ = {𝑎, 𝑏} that ends with a and convert it into
equivalent DFA.
4. Construct a minimal DFA over Σ={𝑎,𝑏}𝑎𝑛𝑑 𝜔∈ (𝑎,𝑏)* such that na(𝜔) ≤2.
5. For a given NFA, Find the equivalent DFA.
6. Write the formal definition of NFA. Construct a NFA which accepts set of all strings
over {a, b} where each string ends with ‘a’.
7. Describe all the steps of Myhill-Nerode Theorem for DFA minimization. For following
given DFA, find the minimized DFA using Myhill-Nerode Theorem.
8. For a given 𝜖𝑁𝐹𝐴, find the NFA.
Unit-II
1. Construct a regular expression corresponding to the finite automata given below using
Arden’s theorem
2. Construct a Moore machine that takes set of all strings over Σ = {𝑎, 𝑏} and counts
number of occurrences of substring ‘baa’.
3. Differentiate between Mea1y machine and Moore machine.
4. Write identities of Regular Expression. Obtain the regular expression for the following
finite automata having q0 and q2 as final states:
5. Find Regular Expression for set of all strings over {a, b} whose length is odd. Obtain
the NFA without epsilon transition corresponding to the following regular expression:
(0* + 1*)* 11(1 *,0*)*.
6. Find Regular Expression for set of all strings over Σ = {𝑎, 𝑏} whose length is at most
two.
7. Prove that the language L= {anbn / n >=1} is not regular using pumping lemma.
8. Write a detailed note on the following:
• Operators of Regular Expression.
• Algebraic laws for Regular Expression
• Pumping Lemma for Regular Languages with suitable examples
• Closure properties of Regular Languages
• Decision Properties of Regular Languages
Unit-III
1. Show that the context-free grammar G given by productions S→SBS/a, B→b is
Ambiguous.
2. Design CFG for the language consisting of all strings of even length over {a, b}.
3. What do you understand by useless symbol in a CFG? Given the following CFG having
S as start symbol, find an equivalent CFG with no useless symbols:
S →AB / AC
A → aAb / bAa / a
B . →bbA / aaB / AB
C → abCa / aDb
D → bD / aC
4. Define CNF. Convert the following Context free Grammar to CNF.
S → a / aA / B
A → aBB / 𝜖
B → Aa / b
5. Construct grammar for set of all strings
6. Write a detailed note on the following:
• Normal Forms of CFG
• Closure properties of CFL
• Decision Properties of CFL
Unit-IV
1. Give formal definition of a PDA.
2. Obtain PDA to accept all strings generated by the language {anbn, n≥ 1}.
3. Construct a PDA equivalent to the following grammar:
S → aAA
A → aS / bS / a
4. Construct PDA for accepting the Language:
L= {wwR : w ∈ {a,b}+ }
5. Write a detailed note on the following:
• Acceptance of String in PDA with empty stack and final state using suitable
examples
• Non-Deterministic PDA with suitable example
Unit-V
1. When a Language is said to be recursive or recursively enumerable?
2. Discuss the concept of Computability.
3. Write short note on the following:
(i) Halting Problem of Turing Machine (ii) Church’s thesis
4. Construct a Turing Machine which accepts set of all strings generated by the Language
L= {anbncn/ n≥ 1}.
5. Write a detailed note on the following:
• Standard Turing Machine
• Turing Machine acting as Adder
• Turing Machine acting as Comparator
• Turing Machine acting as Copier
• Turing Thesis
• Turing Machine with semi-infinite tape
• Multitape Turing Machine
• Jumping Turing Machine
