Probability Engine · CSC257

Theory of Computation (BSc CSIT, CSC257): the questions likely to come

30 analyzed questions from 7 past papers (2074-2081), grouped by syllabus unit — each with its probability, how often it's been asked, and where to study the answer.

7
Papers analyzed
2074-2081
30
Analyzed questions
across 7 syllabus units
4
Very likely units
high-probability topics
5
Units = 80% of marks
study these first
Model answers for this subject are being written. Every question links to its original paper so you can study from the source meanwhile.
Pick a unit
U4 · Q1/7 · 208010 marks
Context-Free Grammars and Languages

Define context-free grammar (CFG). Convert the following CFG into an equivalent grammar in Chomsky Normal Form (CNF): S -> ASA | aB, A -> B | S, B -> b | epsilon.

32%
Possible to appearAppeared in 2 of the last 2 board papers
Seen in
How well do you know this?rating moves you on
MODEL ANSWERU4 · 10 marks

Context-Free Grammar (CFG)

A CFG is a 4-tuple G=(V,T,P,S)G = (V, T, P, S) where VV is a finite set of variables (non-terminals), TT is a finite set of terminals (V∩T=∅V \cap T = \emptyset), S∈VS \in V is the start symbol, and PP is a finite set of productions of the form A→αA \to \alpha with A∈VA \in V and α∈(V∪T)∗\alpha \in (V \cup T)^*. The language generated is the set of terminal strings derivable from SS.

Chomsky Normal Form (CNF): every production is A→BCA \to BC (two variables) or A→aA \to a (single terminal); S→ϵS \to \epsilon is allowed only if ϵ∈L\epsilon \in L.

Converting the given CFG to CNF

Grammar:

S→ASA∣aB,A→B∣S,B→b∣ϵS \to ASA \mid aB, \quad A \to B \mid S, \quad B \to b \mid \epsilon

Step 1: Add a new start symbol

S0→S,S→ASA∣aB,A→B∣S,B→b∣ϵS_0 \to S, \quad S \to ASA \mid aB, \quad A \to B \mid S, \quad B \to b \mid \epsilon

Step 2: Remove ϵ\epsilon-productions

Nullable variable: BB (since B→ϵB \to \epsilon), and hence AA (since A→BA \to B). Remove B→ϵB \to \epsilon and add versions of rules with nullable symbols omitted.

  • S→ASAS \to ASA: dropping nullable AA's gives S→SA∣AS∣SS \to SA \mid AS \mid S. Drop the unit S→SS\to S. So S→ASA∣SA∣ASS \to ASA \mid SA \mid AS.
  • S→aBS \to aB: gives S→aB∣aS \to aB \mid a.
  • A→BA \to B stays; A→ϵA \to \epsilon would appear (A nullable) but we drop it.

Result:

S0→SS_0 \to S S→ASA∣SA∣AS∣aB∣aS \to ASA \mid SA \mid AS \mid aB \mid a A→B∣SA \to B \mid S B→bB \to b

Step 3: Remove unit productions

Unit pairs: S0→SS_0 \to S, A→BA \to B, A→SA \to S.

  • S0→ASA∣SA∣AS∣aB∣aS_0 \to ASA \mid SA \mid AS \mid aB \mid a
  • A→bA \to b (from A→B→bA\to B\to b), and A→ASA∣SA∣AS∣aB∣aA \to ASA \mid SA \mid AS \mid aB \mid a (from A→SA\to S).

Result:

S0→ASA∣SA∣AS∣aB∣aS_0 \to ASA \mid SA \mid AS \mid aB \mid a S→ASA∣SA∣AS∣aB∣aS \to ASA \mid SA \mid AS \mid aB \mid a A→ASA∣SA∣AS∣aB∣a∣bA \to ASA \mid SA \mid AS \mid aB \mid a \mid b B→bB \to b

Step 4: Replace terminals in long rules

Introduce Xa→aX_a \to a. Replace a in aBaB by XaX_a:  →XaB\,\to X_aB.

Step 5: Break rules longer than two symbols

For each ASAASA introduce Y→SAY \to SA, so ASA→AYASA \to A Y with Y→SAY \to SA.

Final CNF Grammar

S0→AY∣SA∣AS∣XaB∣aS_0 \to AY \mid SA \mid AS \mid X_aB \mid a S→AY∣SA∣AS∣XaB∣aS \to AY \mid SA \mid AS \mid X_aB \mid a A→AY∣SA∣AS∣XaB∣a∣bA \to AY \mid SA \mid AS \mid X_aB \mid a \mid b B→bB \to b Xa→aX_a \to a Y→SAY \to SA

Every production now has the form A→BCA \to BC or A→aA \to a, so the grammar is in Chomsky Normal Form.

AI-generated answer · unverifiedView in 2080 paper →
U4 · Question 1 of 7
Question Priority · U4ranked by appearance likelihood — study top-down

Context-Free Grammars and Languages

Analyzed next59%
1
★ TOP PICK

Define context-free grammar (CFG). Convert the following CFG into an equivalent grammar in Chomsky Normal Form (CNF): S -> ASA | aB, A -> B | S, B -> b | epsilon.

10 marksSEEN IN
32%
2

Explain the conversion of a CFG into Greibach Normal Form (GNF).

5 marksSEEN IN
59%
3

What is an ambiguous grammar? Show with an example that a grammar is ambiguous.

5 marksSEEN IN
50%
4

Eliminate left recursion from the grammar A -> Aa | b.

5 marksSEEN IN
50%
5

State and prove the Pumping Lemma for context-free languages. Use it to show that L = { a^i b^j c^k | i = j = k } is not context-free.

10 marksSEEN IN
24%
6

Explain the Chomsky hierarchy of languages with the corresponding grammars and recognizing machines. Discuss the closure properties of context-free languages.

10 marksSEEN IN
22%
7

What is the membership problem? Explain the CYK algorithm in brief.

5 marksSEEN IN
44%
03The mock

Sit a probable paper

A full mock exam built from the most likely questions, mirroring the real paper's structure. Every slot is a real past question.

Most Probable Paper

Mirrors the real structure · 60 marks · based on 7 past papers

Section A: Long Answer QuestionsAttempt any TWO questions.
  1. 1.

    Define a Turing Machine formally. Design a Turing Machine that accepts the language L = { a^n b^n c^n | n >= 1 } and explain its working with a transition diagram.

    [10 marks]
    Turing MachinesLikelyfrom 2081 paper →

    This question has recurred in 3 of 7 years; so far only in internal assessments, not the board; and its topic recurs in 5 of 7 years.

  2. 2.

    Define context-free grammar (CFG). Convert the following CFG into an equivalent grammar in Chomsky Normal Form (CNF): S -> ASA | aB, A -> B | S, B -> b | epsilon.

    [10 marks]
    Context-Free Grammars and LanguagesVery likelyfrom 2080 paper →

    This question has recurred in 2 of 7 years; so far only in internal assessments, not the board; and its topic (Context-Free Grammars and Languages) appears in 100% of years.

  3. 3.

    Explain the relationship between regular expressions and finite automata. Show that for every regular expression there is an epsilon-NFA accepting the same language, and convert (a+b)*ab into an equivalent finite automaton.

    [10 marks]
    Regular Expressions and LanguagesVery likelyfrom 2081 paper →

    This question has recurred in 2 of 7 years; so far only in internal assessments, not the board; and its topic (Regular Expressions and Languages) appears in 100% of years.

Section B: Short Answer QuestionsAttempt any EIGHT questions.
  1. 1.

    Explain the conversion of a CFG into Greibach Normal Form (GNF).

    [5 marks]
    Context-Free Grammars and LanguagesVery likelyfrom 2081 paper →

    This question has recurred in 5 of 7 years; so far only in internal assessments, not the board; and its topic (Context-Free Grammars and Languages) appears in 100% of years.

  2. 2.

    What is an ambiguous grammar? Show with an example that a grammar is ambiguous.

    [5 marks]
    Context-Free Grammars and LanguagesVery likelyfrom 2081 paper →

    This question has recurred in 4 of 7 years; so far only in internal assessments, not the board; and its topic (Context-Free Grammars and Languages) appears in 100% of years.

  3. 3.

    Eliminate left recursion from the grammar A -> Aa | b.

    [5 marks]
    Context-Free Grammars and LanguagesVery likelyfrom 2081 paper →

    This question has recurred in 4 of 7 years; so far only in internal assessments, not the board; and its topic (Context-Free Grammars and Languages) appears in 100% of years.

  4. 4.

    Explain the closure properties of regular languages.

    [5 marks]
    Regular Expressions and LanguagesVery likelyfrom 2081 paper →

    This question has recurred in 4 of 7 years; so far only in internal assessments, not the board; and its topic (Regular Expressions and Languages) appears in 100% of years.

  5. 5.

    Write a regular expression for strings over {0,1} that contain at least one '0' and at least one '1'.

    [5 marks]
    Regular Expressions and LanguagesVery likelyfrom 2080 paper →

    This question has recurred in 4 of 7 years; so far only in internal assessments, not the board; and its topic (Regular Expressions and Languages) appears in 100% of years.

  6. 6.

    Differentiate between recursive and recursively enumerable languages.

    [5 marks]
    Undecidability and Computational ComplexityVery likelyfrom 2081 paper →

    This question has recurred in 4 of 7 years; so far only in internal assessments, not the board; and its topic (Undecidability and Computational Complexity) appears in 86% of years.

  7. 7.

    Explain the working of a multi-tape Turing Machine.

    [5 marks]
    Turing MachinesLikelyfrom 2081 paper →

    This question has recurred in 4 of 7 years; so far only in internal assessments, not the board; and its topic recurs in 5 of 7 years.

  8. 8.

    What is a Universal Turing Machine? Explain its significance.

    [5 marks]
    Turing MachinesLikelyfrom 2081 paper →

    This question has recurred in 4 of 7 years; so far only in internal assessments, not the board; and its topic recurs in 5 of 7 years.

  9. 9.

    Define instantaneous description (ID) of a PDA and explain acceptance by final state and by empty stack.

    [5 marks]
    Pushdown AutomataLikelyfrom 2081 paper →

    This question has recurred in 4 of 7 years; so far only in internal assessments, not the board; and its topic recurs in 4 of 7 years.

04The receipts

Behind the numbers

The raw evidence the predictions are computed from: marks per unit per year, syllabus weights, trends, and coverage.

Show the heatmap, topic table and coverage analysis

The receipt: marks per unit, per year

Each row is a syllabus unit, each column an exam year, each cell the marks that unit earned that year. Click any cell to see the actual questions behind it.

Marks:nonefew → many
2074
2075
2077
2078
2079
2080
2081
Total
U4Context-Free Grammars and Languages
120
U3Regular Expressions and Languages
110
U2Introduction to Finite Automata
100
U7Undecidability and Computational Complexity
70
U6Turing Machines
70
U5Pushdown Automata
40
U1Basic Foundations
15
#Syllabus unitProbabilityAppearedAvg marksSyllabus weightExam vs syllabusTrendQuestions
1U4Context-Free Grammars and LanguagesVery likely100%
2074207520772078207920802081
17.120%10 lecture hrsBalancedexam 23% · syllabus 20%Steady5 recurring7 total
2U3Regular Expressions and LanguagesVery likely100%
2074207520772078207920802081
15.720%10 lecture hrsBalancedexam 21% · syllabus 20%Steady6 recurring6 total
3U2Introduction to Finite AutomataVery likely86%
207420772078207920802081
16.724%12 lecture hrsBalancedexam 19% · syllabus 24%Steady5 recurring7 total
4U7Undecidability and Computational ComplexityVery likely86%
207520772078207920802081
11.712%6 lecture hrsBalancedexam 13% · syllabus 12%Steady4 recurring4 total
5U6Turing MachinesLikely71%
20752077207820792081
1410%5 lecture hrsBalancedexam 13% · syllabus 10%Steady3 recurring3 total
6U5Pushdown AutomataLikely57%
2075207720792081
108%4 lecture hrsBalancedexam 8% · syllabus 8%Steady2 recurring2 total
7U1Basic FoundationsPossible43%
207420782080
58%4 lecture hrsBalancedexam 3% · syllabus 8%Steady1 recurring1 total

Study smart, not hard

Drag the slider: studying the top 5 units in priority order covers ~90% of all observed marks.

  5. ~80% line

Lecture time vs exam marks

Where the exam pays more than the curriculum spends: ● lectures vs ● exam marks, as a share of the whole course. A long teal-leading bar = high-yield unit.

U4Context-Free Grammars and Languages
20% of lectures → 23% of marks
U3Regular Expressions and Languages
20% of lectures → 21% of marks
U2Introduction to Finite Automata
24% of lectures → 19% of marks
U7Undecidability and Computational Complexity
12% of lectures → 13% of marks
U6Turing Machines
10% of lectures → 13% of marks
U5Pushdown Automata
8% of lectures → 8% of marks
U1Basic Foundations
8% of lectures → 3% of marks

Topics are the official CSC257 syllabus units. Predictions are data-driven probabilities computed from 7 past papers (2074-2081) by mapping each real question to its syllabus unit. They indicate what has historically been likely, not guaranteed questions. Always study the full syllabus.