Theoretical Computer Science
Q1) Attempt any EIGHT of the following (Out of TEN):
(a) If A = {ε}, find the value of |A|.
Answer: |A| = 1 (since the set contains only the empty
string ε).
(b) List all the proper suffixes of the string "0123".
Answer: "123", "23", "3", "" (empty string).
(c) Define Useless symbol.
Answer: A useless symbol in a grammar is a symbol that
does not appear in any derivation of a valid string in the
language.
(d) Give the formal definition of a Turing Machine.
Answer: A Turing Machine (TM) is defined as a 7-tuple
(Q, Σ, Γ, δ, q₀, q_accept, q_reject), where:
Q: Finite set of states
Σ: Input alphabet
Γ: Tape alphabet (includes Σ and blank symbol)
δ: Transition function Q × Γ → Q × Γ × {L, R}
q₀: Start state
q_accept: Accept state
q_reject: Reject state
(e) Define left linear grammar.
Answer: A left-linear grammar is a grammar where all
production rules are of the form:
A → aB or A → a, where A, B are non-terminals and a is a
terminal.
(f) State True or False: DFA does not have multiple final
states.
Answer: False. A DFA can have multiple final states.
(g) Name the type of language accepted by a Pushdown
Automaton (PDA).
Answer: A Pushdown Automaton (PDA) accepts
Context-Free Languages (CFLs).
(h) Write the tuples of LBA.
Answer: A Linear Bounded Automaton (LBA) is a Turing
Machine with limited tape size. It is defined by the 7-
tuple:
(Q, Σ, Γ, δ, q₀, q_accept, q_reject), where the tape size is
bounded by the input length.
(i) State True or False: Pumping lemma is used to show
that a language is not context tree.
Answer: False. The Pumping Lemma is used to prove
that a language is not regular (for Regular Languages) or
not context-free (for CFLs).
(j) Write the smallest possible string accepted by the
following regular expression:
*a(a+b)ab
Answer: aab (smallest string that starts with "a" and
ends with "ab").
Q2) Attempt any FOUR of the following (Out of FIVE):
(a) Explain types of grammar.
According to Chomsky’s Hierarchy:
1. Type 0 (Unrestricted Grammar): Generates Recursively
Enumerable languages.
2. Type 1 (Context-Sensitive Grammar - CSG): Generates
Context-Sensitive languages.
3. Type 2 (Context-Free Grammar - CFG): Generates
Context-Free languages.
4. Type 3 (Regular Grammar): Generates Regular
languages (can be recognized by DFA/NFA).
*(b) Construct FA for regular expression (1+0)0.
Regular Expression: (1+0)*0
Language Description: All binary strings that end with
'0'.
Finite Automaton (DFA):
States: {q0, q1}
Transitions:
q0 --0--> q1
q0 --1--> q0
q1 --0--> q1
q1 --1--> q0
Start state: q0
Final state: q1
(c) Differentiate between CNF and GNF (any two points).
CNF (Chomsky Normal GNF (Greibach Normal
Form) Form)
Each production is of the Each production is of the
form A → BC or A → a form A → aα where a is a
terminal and α is a
sequence of non-terminals
Used in PDA design and Used in Top-Down Parsing
simplification algorithms
(d) Write down the ε-closure of each state from the given
FA.
Solution depends on FA diagram (provide the states and
transitions).
(e) Define types of Turing Machine.
1. Deterministic Turing Machine (DTM)
2. Non-Deterministic Turing Machine (NDTM)
3. Multi-Tape Turing Machine
4. Multi-Track Turing Machine
5. Universal Turing Machine (UTM)
Q3) Attempt any TWO of the following (Out of THREE):
(a) Construct a DFA for L1 ∩ L2
L1 = All strings starting with ‘a’.
L2 = All strings that do not contain 'ab' as a substring.
Steps:
1. Construct DFAs for L1 and L2 separately.
2. Take their intersection using product construction.
(b) Convert CFG to CNF:
Given:
S → aSa | bSb
S → a | b | aa | bb
Steps to convert to CNF:
1. Remove unit productions.
2. Break down long productions into binary rules.
CNF Form:
S → aA | bB | C | D
A→Sa
B→Sb
C → aa
D → bb
(c) Design a TM for L = {WCW^R | W ∈ (0+1)*}
This Turing Machine checks for palindromes with a
middle separator 'C'.
Steps:
1. Scan from left to right, marking first and last
characters.
2. Ensure they match, remove them, and repeat.
3. If only ‘C’ remains, accept.
Q4) Attempt any TWO of the following (Out of THREE):
(a) Construct a PDA for L = {aⁿbⁿcⁿ | n ≥ 0}.
Push ‘a’ onto stack,
Match with ‘b’ by popping,
Ensure matching ‘c’ removes the remaining elements.
(b) Construct a Moore machine for L over {0,1} that
outputs ‘*’ if string contains ‘11’, ‘#’ otherwise.
Moore machine uses state-dependent output.
Two states:
q0 (No '11' yet, outputs ‘#’)
q1 (Saw '11', outputs ‘*’)
(c) Compare DFA and NFA.
DFA NFA
Only one transition per Multiple transitions
state-symbol pair allowed
No ε-moves Can have ε-moves
Harder to construct but Easier to construct but
easier to implement needs conversion for
implementation
Q5) Attempt any ONE of the following (Out of TWO):
(a) Construct a Mealy machine for {0,1} that toggles input.
Output flips 0 → 1 and 1 → 0.
(b) Show that L = {0ⁿ1ⁿ | n ≥ 1} is not regular.
Use Pumping Lemma:
Pick w = 0ⁿ1ⁿ with |w| ≥ p.
Choose xyz where y contains only 0s.
Pump y → Number of 0s ≠ 1s, contradicting L.
Thus, L is not regular.
I'll solve each question from 1 to 5 in the order presented
in the exam paper. Let's get started:
Q1) Attempt any Eight of the following (out of Ten): [8 × 1 =
8]
a) Write the smallest possible string accepted by the
regular expression:
01 (0 + 1) 01*
Answer: The smallest possible string is "01". The
expression starts with "01", followed by zero or more
occurrences of "0" or "1", and ends with "01" repeated zero
or more times.
b) State True or False. PDA accepts only non-regular sets.
Answer: False. A Pushdown Automaton (PDA) can accept
some regular sets as well as context-free languages.
c) Define ambiguous grammar.
Answer: An ambiguous grammar is a context-free grammar
that can generate a single string in multiple ways (i.e., it has
more than one leftmost derivation or parse tree).
d) What are the types of grammar in Chomsky hierarchy?
Answer: The Chomsky hierarchy includes four types of
grammars:
1. Type 0 - Unrestricted Grammar
2. Type 1 - Context-Sensitive Grammar
3. Type 2 - Context-Free Grammar
4. Type 3 - Regular Grammar
e) What is Reduction?
Answer: Reduction is the process of transforming one
problem into another problem in such a way that a
solution to the second problem can be used to solve the
first problem.
f) State True or False. String consists of only Non-Terminal
symbols.
Answer: False. A string in a grammar usually consists of
both terminal and non-terminal symbols.
g) Define non-deterministic Turing machine.
Answer: A non-deterministic Turing machine is a
theoretical model of computation where the machine can
have multiple possible actions from a given state and
symbol, effectively allowing it to branch into multiple
computation paths simultaneously.
h) If A = {𝜖}, find the value of | A |.
Answer: | A | = 1. The set contains one element, the empty
string.
i) Write down the 𝜖-closure of each state from the
following FA.
Answer: (Since the FA is not provided, the general
approach is to list all states reachable from a given state
through 𝜖-transitions.)
j) State two differences between NFA and DFA.
Answer:
1. NFA can have multiple transitions for the same input
from a given state, while DFA has exactly one transition
per input.
2. NFA can have 𝜖 (epsilon) transitions, whereas DFA
cannot.
Q2) Attempt any Four of the following (out of Five): [4 × 2 =
8]
a) Explain two methods for defining language accepted by
PDA.
Answer:
1. Acceptance by Final State: The PDA accepts a string if,
after processing the entire input, it reaches a final state.
2. Acceptance by Empty Stack: The PDA accepts a string if
the stack is empty after processing the input.
b) Explain types of regular grammar.
Answer:
1. Right Linear Grammar: All productions have the form A
→ xB or A → x, where A and B are non-terminals and x is a
terminal.
2. Left Linear Grammar: All productions have the form A →
Bx or A → x.
c) Construct FA for regular expression ((1+0)* + 100)*.**
Answer: The FA will have states to accommodate
repetitions of "0" or "1", as well as the sequence "100".
(Diagram can be drawn, but the description involves a
loop for (0+1)* and a sequence for "100".)
d) Differentiate between Moore and Mealy Machine.
Answer:
1. Output Generation: Moore machine generates output
based on states, while Mealy machine generates output
based on transitions.
2. Response to Input: Mealy machines can react faster to
inputs since output depends directly on transitions.
e) State two differences between TM and LBA.
Answer:
1. Tape Length: TM has an infinite tape length, while LBA
(Linear Bounded Automaton) has tape length bounded
by the input size.
2. Acceptance: TM can accept recursively enumerable
languages, while LBA accepts context-sensitive
languages.
Q3) Attempt any Two of the following (out of Three): [2 × 4
= 8]
a) Construct DFA for language which contains all strings
with exactly 2 consecutive 1's anywhere.
Answer:
The DFA will have states to track:
1. No "11" seen
2. One "1" seen
3. Two consecutive "1"s seen (final state)
The DFA transitions between these states based on
input "0" and "1".
b) Convert the following CFG into CNF:
S → XYX, X → aX/𝜖, Y → bY/𝜖
Answer:
1. Eliminate 𝜖-productions and unit productions.
2. Ensure that productions are in the form of A → BC or A →
a.
c) Design TM for language L = {a^m b^n / n ≥ m and m ≥ 1}
Answer:
1. Start by marking each "a" and matching it with "b".
2. Continue until all "a"s are matched with "b"s.
3. Accept if the number of "b"s is equal or greater than
"a"s.
Q4) Attempt any Two of the following (out of Three): [2 × 4
= 8]
a) Construct a PDA for the language {w / na(w) = nb(w)}
(number of a's equal to number of b's).
Answer:
1. Push "a" on the stack.
2. Pop for each "b".
3. Accept if the stack is empty at the end.
b) Construct Moore machine which outputs even or odd
according to the number of a's encountered.
Answer:
1. Two states: Even and Odd.
2. Transition between states on input "a".
3. State output shows "Even" or "Odd".
c) Construct equivalent DFA for the following NFA.
Answer:
1. Use the subset construction method to convert the
given NFA to DFA.
2. Combine states to handle multiple transitions.
Q5) Attempt any One of the following (out of Two): [1 × 3 =
3]
a) Show that L = {O^n 1^n O^n} is not regular.
Answer:
Use the Pumping Lemma for regular languages to prove
non-regularity. The contradiction occurs because the
number of "O"s and "1"s cannot be maintained after
pumping.
b) Eliminate 𝜖-production for grammar & also find nullable
variable:
S → AB, A → SA/BB/bB, B → b/aA/𝜖
Answer:
1. Nullable variables: B
2. Eliminating 𝜖-productions involves removing nullable
variables and updating the productions accordingly.
Let's solve the questions from the uploaded Theoretical
Computer Science (TOC) April 2022 exam paper one by
one.
Q1) Attempt any Eight of the following (out of TEN) [8 × 1 = 8]
a) Write output function λ of Moore and Mealy machines.
Moore Machine: The output function λ maps states to
outputs, i.e., λ: Q → Σ.
Mealy Machine: The output function λ maps transitions
(state and input) to outputs, i.e., λ: Q × Σ → Σ.
b) List all the proper prefixes of the string "ABCD".
Proper prefixes of "ABCD":
1. 𝜖 (empty string)
2. A
3. AB
4. ABC
c) Define Nullable symbol.
A Nullable symbol in a grammar is a non-terminal that
can derive the empty string (𝜖).
d) Give formal definition of Pushdown Automata.
A Pushdown Automaton (PDA) is a 7-tuple:
M=(Q,Σ,Γ,δ,q0,Z0,F)M = (Q, \Sigma, \Gamma, \delta, q_0,
Z_0, F)
where:
Q: Finite set of states
Σ: Input alphabet
Γ: Stack alphabet
δ: Transition function
q0q_0: Initial state
Z0Z_0: Initial stack symbol
F: Set of final states
e) Define right linear grammar.
A Right Linear Grammar is a grammar where each
production rule has the form:
A→xBA \rightarrow xB or A→xA \rightarrow x, where A
and B are non-terminals and x is a terminal.
f) State True or False. DFA do not have multiple final
states.
False. A DFA can have multiple final states.
g) Name the type of language accepted by Turing
Machine.
Recursively Enumerable Languages
h) Write the tuples of LBA.
A Linear Bounded Automaton (LBA) is a 7-tuple:
M=(Q,Σ,Γ,δ,q0,F,B)M = (Q, \Sigma, \Gamma, \delta, q_0, F,
B)
where:
Q: Finite set of states
Σ: Input alphabet
Γ: Tape alphabet
δ: Transition function
q0q_0: Initial state
F: Set of final states
B: Blank symbol
i) State true or false. Pumping lemma is used to show that
language is not context-free.
True. The pumping lemma for context-free languages
helps prove that a language is not context-free.
j) Write smallest possible string accepted by the following
regular expression:
l0+(0+l1)0∗1l0+(0+l1)0*1
The smallest string accepted is "01".
Q2) Attempt any Four of the following [4 × 2 = 8]
a) Explain Reduction with the help of an example.
Reduction is transforming one problem into another to
prove something about the original problem.
Example: Halting Problem Reduction: To prove that the
Halting Problem is undecidable, reduce it from the
Acceptance Problem.
b) Construct FA for regular expression
(0l+l0)∗+11(0l+l0)*+ 11.
The FA will have states to handle the repeating patterns
of "0l" and "l0", and an additional part to handle "11".
The FA will transition based on input "0" or "1" and
accept "11" separately.
c) Differentiate between DFA and NFA.
1. Transition: DFA has a single transition for each symbol
from a state, while NFA can have multiple transitions.
2. Epsilon Moves: NFA can have epsilon (𝜖) moves, but DFA
cannot.
d) Write down the ∈-closure of each state from the given
FA.
(Since the FA is not provided, the ∈-closure involves
finding all states reachable via epsilon transitions from a
given state.)
e) Define types of Turing Machine.
1. Deterministic Turing Machine (DTM)
2. Non-Deterministic Turing Machine (NDTM)
3. Multi-tape Turing Machine
4. Multi-track Turing Machine
5. Universal Turing Machine
Q3) Attempt any Two of the following [2 × 4 = 8]
a) Construct DFA for language over Σ = {0,1}, where L1∩L2:
L1 = {All strings starting with ‘0’}
L2 = {All strings not having ‘01’ as substring}
The DFA will have states to track whether the string
starts with "0" and ensures no "01" substring appears.
b) Construct the CFG in Chomsky Normal Form (CNF):
S→aSa∣bSb∣a∣b∣aa∣bbS \rightarrow aSa | bSb | a | b|
aa | bb
Convert the CFG by eliminating non-CNF rules and
ensuring binary productions and terminal-only
productions.
c) Construct TM which accepts the language that starts
with 0 and ends with 1.
The TM will check for the first and last symbols:
1. Move right while checking the first symbol is "0".
2. Move to the end and check if the last symbol is "1".
3. Accept if both conditions are met.
Q4) Attempt any Two of the following [2 × 4 = 8]
a) Construct a PDA for the language L = {aⁿbⁿ | n ≥ 1}
Push "a" on the stack for each input "a".
Pop from the stack for each "b".
Accept if the stack is empty after all input.
b) Construct a Mealy machine for language L over Σ = {0,
1}:
Outputs ‘A’ if it has substring "101".
Outputs ‘B’ if it has substring "110".
Otherwise, outputs ‘C’.
States track the presence of substrings and update the
output accordingly.
c) Write a short note on Chomsky’s hierarchy.
Type 0: Unrestricted Grammar (Recursively Enumerable)
Type 1: Context-Sensitive Grammar
Type 2: Context-Free Grammar
Type 3: Regular Grammar
Each type has specific production rules and complexity.
Q5) Attempt any One of the following [1 × 3 = 3]
a) Construct a Moore machine over alphabet {0,1} to get
1’s complement of a binary string.
Each state produces the opposite of the current binary
digit:
State "0" outputs "1".
State "1" outputs "0".
The output is the complement of the input binary string.
b) Show that L = {0ⁿ1ⁿ | n ≥ 1} is not regular.
Use the Pumping Lemma for Regular Languages:
Assume L is regular.
Choose a string "0ⁿ1ⁿ" where n is large.
After pumping, the number of "0"s and "1"s will not
remain equal, contradicting the language's definition.
Hence, L is not regular.
Let's solve the questions from the Theoretical Computer
Science (TOC) Oct 2023 exam paper.
Q1) Attempt any Eight of the following (Out of TEN) [8 × 1 = 8]
a) Define Unit production of grammar.
A Unit Production in a grammar is a production rule of
the form:
A→BA \rightarrow B
where AA and BB are non-terminal symbols. It means
that one non-terminal can directly derive another non-
terminal.
b) Construct Mealy machine which toggles its input.
A Mealy machine that toggles the input will have two
states:
State 0: If input is "0", output "1"; if input is "1", output
"0".
State 1: Similar behavior but remains in the same
state.
The output is the inverse (complement) of the input at
each step.
c) Explain proper Suffix and Prefix of a string with one
example.
Proper Prefix: A prefix that is a substring from the start
but does not include the entire string.
Example: For string "ABCD", proper prefixes are: 𝜖, A, AB,
ABC
Proper Suffix: A suffix that is a substring from the end
but does not include the entire string.
Example: For string "ABCD", proper suffixes are: 𝜖, D, CD,
BCD
d) Give formal definition of Pushdown Automata.
A Pushdown Automaton (PDA) is a 7-tuple:
M=(Q,Σ,Γ,δ,q0,Z0,F)M = (Q, \Sigma, \Gamma, \delta, q_0,
Z_0, F)
where:
QQ: Finite set of states
Σ\Sigma: Input alphabet
Γ\Gamma: Stack alphabet
δ\delta: Transition function
q0q_0: Initial state
Z0Z_0: Initial stack symbol
FF: Set of accepting states
e) Define left linear and right linear grammar.
Left Linear Grammar: All productions are of the form
A→xBA \rightarrow xB or A→xA \rightarrow x, where xx is
a terminal.
Right Linear Grammar: All productions are of the form
A→BxA \rightarrow Bx or A→xA \rightarrow x, where xx is
a terminal.
f) State True or False. Finite Automata has an infinite
number of states.
False. A Finite Automaton has a finite number of states
by definition.
g) Name the types of normal forms of grammar.
The types of normal forms are:
1. Chomsky Normal Form (CNF)
2. Greibach Normal Form (GNF)
h) Write the tuples of LBA.
A Linear Bounded Automaton (LBA) is a 7-tuple:
M=(Q,Σ,Γ,δ,q0,F,B)M = (Q, \Sigma, \Gamma, \delta, q_0, F,
B)
where:
QQ: Finite set of states
Σ\Sigma: Input alphabet
Γ\Gamma: Tape alphabet
δ\delta: Transition function
q0q_0: Initial state
FF: Set of final states
BB: Blank symbol
i) State true or false. Pumping lemma is used to show that
language is not context tree.
False. Pumping lemma is used to show that a language is
not context-free.
j) Write smallest possible string accepted by the following
regular expression:
10+(0+11)0∗110 + (0 + 11)0*1
The smallest string accepted is "01".
Q2) Attempt any Four of the following (Out of FIVE) [4 × 2 = 8]
a) Explain types of grammar.
Type 0: Unrestricted Grammar (Recursively Enumerable)
Type 1: Context-Sensitive Grammar
Type 2: Context-Free Grammar
Type 3: Regular Grammar
The classification is based on the form of production
rules and language complexity.
b) Construct FA for the regular expression
(01+10)∗+11(01+10)*+11
The FA will have states to handle repeating patterns "01"
and "10", and a separate path for "11".
The FA will accept any combination of "01" or "10"
repeated, and the string "11" as well.
c) Differentiate between FA and PDA.
1. Memory:
FA: No memory (no stack).
PDA: Uses a stack to store intermediate symbols.
2. Language:
FA: Regular languages.
PDA: Context-free languages.
d) Write down the ε-closure of each state from the given
FA.
ε-closure of a state is the set of all states reachable
through ε-transitions from that state.
(Since the specific FA is not provided, we compute the
closure by finding states connected via ε).
e) Define types of Turing Machine.
1. Deterministic Turing Machine (DTM)
2. Non-Deterministic Turing Machine (NDTM)
3. Multi-tape Turing Machine
4. Multi-track Turing Machine
5. Universal Turing Machine
Q3) Attempt any Two of the following (Out of THREE) [2 × 4 = 8]
a) Construct DFA for the language:
L1∩L2:
L1: Strings starting with 'a'.
L2: Strings not containing 'ab' as a substring.
Combine both conditions to build the DFA.
b) Convert the given CFG into CNF:
S→ABAS \rightarrow ABA
A→aA∣ϵA \rightarrow aA \mid \epsilon
B→bB∣ϵB \rightarrow bB \mid \epsilon
Apply the CNF conversion steps to eliminate epsilon
and ensure binary productions.
c) Design TM for the language:
L={WCWR∣W is in (0+1)∗}L = \{ WCWR \mid W \text{ is in }
(0+1)* \}
The TM reads a string, checks for symmetry around the
center, and accepts if the reverse is the same.
Q4) Attempt any Two of the following (Out of THREE) [2 × 4 = 8]
a) Construct a PDA for the language:
L={0n1m2n+m∣n,m≥1}L = \{0^n1^m2^{n+m} \mid n, m \geq
1 \}
Push "0"s to the stack, pop for "1"s, and then check the
combined count for "2"s.
b) Construct a Moore machine to detect '11' and output ‘*’
otherwise '#’.
The machine changes state when it sees the substring
"11" and outputs accordingly.
c) Compare DFA and NFA:
1. Determinism: DFA has one transition per input, while
NFA can have multiple or epsilon transitions.
2. Efficiency: DFA is faster in execution as it has
deterministic paths, while NFA can have multiple
possible paths.
Q5) Attempt any One of the following (Out of TWO) [1 × 3 = 3]
a) Construct a Mealy machine to convert "101" to "100":
Track the occurrence of the substring "101" and replace
the last '1' with '0'.
b) Show that L = {0ⁿ1ⁿ | n ≥ 1} is not regular:
Use the Pumping Lemma to prove the non-regularity by
showing that any pumped string violates the language
property.
