TOC SEPERATE QUESTIONS

MODULE–1 — SEPARATE QUESTIONS (ALL PAPERS)

1) Model Ques on Paper-1 (2022–23)

Q.01 (a)
Obtain a DFA to accept strings of a’s and b’s having odd number of a’s and even number of b’s.

Q.01 (b)
Draw a DFA to accept decimal strings divisible by 3.

Q.01 (c)
Define the following terms with example:
i) Alphabet
ii) Power of Alphabet
iii) Languages

Q.02 (a)
Obtain an ε-NFA which accepts strings consis ng of zero or more a’s followed by zero or more b’s followed by zero or
more c’s.

Q.02 (b)
Define Determinis c Finite Automata. Explain the two preferred nota ons for describing the transi on func on with
an example.

Q.02 (c)
Obtain a DFA for the given NFA using lazy evalua on method.

2) Model Ques on Paper-2 (2024–25)

Q.01 (a)
i) Design a DFA to accept strings of a’s and b’s where
L = { |W| mod 5 = |W| mod 4 }
ii) Design a DFA to accept strings of 0’s and 1’s where
L = { star ng with 01 or star ng with 10 }

Q.01 (b)
Define NFA. Convert the given NFA to its equivalent DFA.

Q.02 (a)
Find ε-closure of all the states and convert the given NFA to DFA.

Q.02 (b)
i) Define alphabets, strings and languages.
ii) Construct a DFA to accept strings of 0’s and 1’s star ng with at least two 0’s and ending with at least two 1’s.

3) Dec 2024 / Jan 2025 Examina on

Q.01 (a)
Define the following with example:
i) Language
ii) String
iii) Power of an alphabet

Q.01 (b)
Define DFA. Draw a DFA that accepts:
i) All strings that contain a substring “aba”
ii) Strings of a’s and b’s that contain not more than three b’s
iii) L = { w ∈ {a, b}* : No two consecu ve characters are same }

Q.01 (c)
Convert the given NFA to DFA.

Q.02 (a)
Define the following with example:
i) Alphabet
ii) Reversal of string
iii) Concatena on of languages

Q.02 (b)
Design a DFA for the language
L = { w ∈ {0,1}* : w is divisible by 5 }

Q.02 (c)
Define NFA. Obtain an ε-NFA which accepts strings consis ng of 0 or more a’s followed by 0 or more b’s followed by 0
or more c’s. Also convert it to DFA.

4) June / July 2025 Examina on

Q.01 (a)
Define the following with an example:
i) Alphabet
ii) Power of an alphabet
iii) String concatena on
iv) Language

Q.01 (b)
Define Determinis c Finite Automata (DFA) and the language accepted by it.

Q.01 (c)
Design a DFA to accept the following languages:
i) L = { w ∈ {0,1}* : w has 001 as a substring }
ii) L = { w ∈ {0,1}* : |w| mod 3 = 0 }

Q.02 (a)
Convert the given NFA to DFA.

Q.02 (b)
Convert the given ε-NFA to DFA and define ε-NFA.
 MODULE–2 — SEPARATE QUESTIONS (ALL PAPERS)

1) Model Ques on Paper-1 (2022–23)

Q.03 (a)
List applica ons of Regular Expressions. What are the nota ons used in UNIX opera ng system? List a few regular
expressions with UNIX nota ons.

Q.03 (b)
Obtain an ε-NFA for the regular expression (a + b)* bb (a + b)*.

Q.03 (c)
Find the minimized DFA of the given automaton.

Q.04 (a)
Define Pumping Lemma. Prove that the language
L = { aⁱ bʲ | i > j } is not regular.

Q.04 (b)
Develop regular expressions for the following languages on Σ = {a, b}:
i) Strings whose fi h symbol from the right end is a
ii) Strings containing not more than three a’s

Q.04 (c)
Find the regular language accepted by the given FA by elimina ng states.

2) Model Ques on Paper-2 (2024–25)

Q.03 (a)
i) Define regular expressions.
ii) Obtain RE to accept strings of a’s and b’s whose second symbol from the right end is a.
iii) Obtain RE to accept words with two or more le ers beginning and ending with the same le er.
iv) Obtain NFA which accepts strings of a’s and b’s star ng with “ab”.
v) Obtain NFA for the regular expression (a + b)* aa (a + b)*.

Q.03 (b)
Minimize the given DFA using table filling algorithm.

Q.04 (a)
i) State and prove Pumping Lemma theorem.
ii) Show that L = { WWᴿ | W ∈ {a,b}* } is not regular.

Q.04 (b)
Show that regular languages are closed under:
i) Union, concatena on and Kleene star
ii) Intersec on and difference

3) Dec 2024 / Jan 2025 Examina on

Q.03 (a)
Define regular expression. Write the regular expression for the following languages:
i) Strings of a’s and b’s star ng with a and ending with b
ii) Strings of alterna ng 0’s and 1’s
iii) L = { aᵐ bⁿ | (n + m) is even }
iv) L = { w : |w| mod 3 = 0 }

Q.03 (b)
Minimize the given finite automaton using table filling algorithm.

Q.04 (a)
Construct ε-NFA for the given regular expressions.

Q.04 (b)
Obtain the regular expression deno ng the language accepted by the given FA using Kleene’s theorem.

Q.04 (c)
State the Pumping Lemma for regular languages and prove that the given languages are not regular.

June / July 2025 Examina on

Q.03 (a)
Define regular expression. Write the regular expression for the following languages:
i) Represen ng strings of a’s and b’s having odd length
ii) To accept 10 as substring over alphabet Σ = {0,1}

Q.03 (b)
State and prove pumping lemma for regular languages.
 MODULE–3 — SEPARATE QUESTIONS (ALL PAPERS)

1) Model Ques on Paper-1 (2022–23)

Q.05 (a)
What is ambiguous grammar? Explain techniques for reducing ambiguity with suitable examples.

Q.05 (b)
Show that the grammar
S → aS | aSbS | ε
is ambiguous for the string “aab”.

Q.05 (c)
Design CFG for the following languages:
i) Strings with no more than three a’s over Σ = {a,b}
ii) Strings with any number of a’s and b’s with at least one a

Q.06 (a)
For the given grammar, obtain the corresponding PDA.

Q.06 (b)
For the grammar given, find deriva on tree, le most deriva on and rightmost deriva on for the string “aabbabab”.

Q.06 (c)
Define CFG. Design CFG for:
i) Non-palindromes over {a,b}
ii) L = { 0ⁿ1ⁿ⁺¹ | n ≥ 0 }
iii) L = { wcwᴿ | w ∈ {a,b}* }

2) Model Ques on Paper-2 (2024–25)

Q.05 (a)
i) Obtain unambiguous grammar and deriva on for (a+b)*(a−b).
ii) Give LMD, RMD and parse tree for the string “aaabab”.

Q.05 (b)
Design a PDA to accept palindrome language
L = { wcwᴿ | w ∈ (a+b)* } and show ID for string “aab”.

Q.06 (a)
Construct CFG for the following languages:
i) L = { 0²ⁿ1ᵐ | n ≥ 0, m ≥ 0 }
ii) L = { WWᴿ | W ∈ {a,b}* }
iii) Strings containing substring “101”
iv) Equal number of a’s and b’s
v) Strings of 0’s and 1’s containing substring 000

Q.06 (b)
Define with example:
i) Grammar
ii) Deriva on
iii) Le most and rightmost deriva on
iv) Ambiguous grammar
v) Parse tree

3) Dec 2024 / Jan 2025 Examina on

Q.05 (a)
Design CFG for the following languages.

Q.05 (b)
Consider the grammar given and answer:
i) LMD
ii) RMD
iii) Parse tree
iv) Check whether grammar is ambiguous.

Q.06 (a)
Define CFG, le most deriva on, parse tree and ambiguous grammar.

Q.06 (b)
Design PDA for the given language and show moves for the given string.

June / July 2025 Examina on

Q.05 (a)
Define context free grammar. Write the CFG for the following languages:
i) L = { aⁿbⁿcᵐ | n ≥ 0 }
ii) L = { w ∈ {a,b}* : nₐ(w) = nᵦ(w) }

Q.05 (b)
Define ambiguous grammar with suitable example.
Given the grammar:
E → E + E | E − E | E * E | E / E | (E) | I
Find the le most deriva on, rightmost deriva on, and parse tree for the string.
 MODULE–4 — SEPARATE QUESTIONS (ALL PAPERS)

1) Model Ques on Paper-1 (2022–23)

Q.07 (a)
Define the following with suitable examples:
i) Inherently ambiguous language
ii) Chomsky Normal Form
iii) Greibach Normal Form

Q.07 (b)
Remove all the ε-produc ons and unit produc ons from the grammar:
S → aA | aBB
A → aAA | ε
B → bB | bbC
C→B

Q.07 (c)
Define Greibach Normal Form. Convert the following grammar into GNF:
S → AB1 | 0
A → 00A | B
B → 1A1

Q.08 (a)
Write the LMD, RMD and parse tree for the string +*-xyxy using the grammar:
E → +EE | *EE | −EE | x | y

Q.08 (b)
Obtain the following grammar in CNF:
S → ASB | ε
A → aAS | a
B → SbS | A | bb

Q.08 (c)
Define CNF. Convert the following grammar into CNF:
S → 0A | 1B
A → 0AA | 1S | 1
B → 1BB | 0S | 0

2) Model Ques on Paper-2 (2024–25)

Q.07 (a)
Convert the following grammar into CNF:
S → a | aA | B
A → aBB | ε
B → Aa | b

Q.07 (b)
Eliminate le recursion from the grammar:
S → Sa | Sb | aA | B
A → Ab | aBB | a | b
B → Ba | bb

Q.08 (a)
Convert the following grammar into GNF:
A → BC
B → CA | a
C → AB | b

Q.08 (b)
Show that context-free languages are not closed under:
i) Union
ii) Concatena on
iii) Star
iv) Complementa on

3) Dec 2024 / Jan 2025 Examina on

Q.07 (a)
Define CNF. Convert the following CFG to CNF:
E→E+T|T
T→T*F|F
F → (E) | I
I→a|b

Q.07 (b)
Show that the language
L = { 0ⁿ1²ⁿ | n ≥ 1 }
is not context free.

Q.07 (c)
Prove that the family of context-free languages is closed under:
i) Union
ii) Concatena on

Q.08 (a)
Define Greibach Normal Form. Convert the following CFG into GNF:
S → AB
A → aA | bB | b
B→b

Q.08 (b)
Consider the following CFG:
S → ABC | BaB
A → aA | ε
B → bBb | b | ε
C → CA | AC
D→ε

i) What are useless symbols?

Q.08 (c)
Prove that the following languages are not context free:
i) L = { aⁱ | i is prime }
ii) L = { aⁿ | n ≥ 1 }
 4) June / July 2025 Examina on

Q.07 (a)
Convert the following grammar into Chomsky Normal Form (CNF):
S → ASB | a
A → aAS | a
B → SbS | bb

Q.07 (b)
State and prove the pumping lemma for context-free languages.

Q.08 (a)
What are useless symbols and ε-produc ons?
Eliminate ε-produc ons, unit produc ons and useless symbols from the grammar:
A → bA | Ba / aa
B → aBa / b
C → CA / AC / B
D→a/ε

Q.08 (b)
Prove that the family of context-free languages is closed under:
i) Union
ii) Concatena on
iii) Star closure
 MODULE–5 — SEPARATE QUESTIONS (ALL PAPERS)

1) Model Ques on Paper-1 (2022–23)

Q.09 (a)
Define Turing Machine. With a neat block diagram, explain the working of a basic Turing Machine.

Q.09 (b)
Design a Turing Machine to accept all palindromes over {a,b}*.
Draw the transi on table and transi on diagram.
Show the sequence of IDs for the string “ababa”.

Q.09 (c)
Write short notes on:
i) Mul tape Turing Machine
ii) Nondeterminis c Turing Machine

Q.10 (a)
Briefly explain the techniques for Turing Machine construc on.
Also write applica ons of Turing Machine.

Q.10 (b)
Design a Turing Machine to accept the language
L = { aⁿbⁿ | n ≥ 1 }.
Draw the transi on diagram and show the moves for the string “aaaabbbb”.

Q.10 (c)
Design a Turing Machine to accept strings formed over {0,1}* and ending with 000.
Write the transi on diagram and show the sequence of IDs for w = 101000.

2) Model Ques on Paper-2 (2024–25)

Q.09 (a)
Explain the Church–Turing thesis with a neat diagram.
Explain Mul tape Turing Machine with a neat diagram.

Q.09 (b)
Define Turing Machine. Design a TM for the language
L = { 0ⁿ1ⁿ | n ≥ 0 }.
Show that the string 0011 is accepted.

Q.10 (a)
Define Turing Machine. Design a TM for the language
L = { 1ⁿ2ⁿ3ⁿ | n ≥ 1 }.
Show that the string 111222333 is accepted.

Q.10 (b)
Demonstrate the model of Linear Bounded Automata (LBA) with neat diagram.

3) Dec 2024 / Jan 2025 Examina on

Q.09 (b)
Design a Turing Machine to accept the language
L = { aⁿbⁿcⁿ | n ≥ 1 }.
Draw the transi on diagram and show the moves for the string aabbcc.

Q.10 (a)
Design a Turing Machine to accept palindrome over {a,b} and draw the transi on diagram.

Q.10 (b)
Write short notes on:
i) Recursively enumerable language
ii) Mul tape Turing Machine

4) June / July 2025 Examina on

Q.09 (a)
Define Turing Machine. Explain the working and variants of Turing Machine.

Q.09 (b)
Design a Turing Machine to accept the language
L = { aⁿbⁿcⁿ | n ≥ 0 }.
Draw the transi on diagram and show the moves for the string aabbcc.

Q.10 (a)
Explain language acceptability and steps involved in designing a Turing Machine.

Q.10 (b)
Explain the following:
i) Programming techniques for Turing Machines
ii) Undecidability problem