Mumbai University Solved Question Papers
Theory of Computation
Previous Year Question Paper with Solution
BSc CS · Sem 3
Oct 2025 Examination
munotes.in
Mumbai
BSc CS Sem 3 Theory of Computation Oct 2025 Question Paper with Solutions
Get access to whole semester resourcesSemester Pass
MU B.Sc. (Computer Science) student group
Free to join
First published on munotes.in on 16 October 2026.
Published by munotes.in, Mumbai.
Model answers written and edited by the munotes.in editorial desk.
Passages from this volume may be quoted, in print, online or by an AI system, with credit: name munotes.in and link to this volume's page. The volume may not be reproduced as a whole. Full terms at munotes.in/content-license.
munotes.in is an independent study resource for students of the University of Mumbai. It is not affiliated with the University of Mumbai, and is not endorsed by it.
The University does not publish an official answer key for this paper. The answers in this volume are model answers, written to show how a full-mark answer is built. They are a study aid, not an authority on what an examiner marked.
The question paper reproduced here is the paper as set by the University of Mumbai at the Oct 2025 examination.
Contents
The questions below are the paper as the University of Mumbai set it at the Oct 2025 examination, in the order it was set.
MarksPage
The Paper as Set
The questions in this volume are the questions asked at the Oct 2025 examination, reproduced as the University of Mumbai set them, in the order it set them. Nothing has been reworded, added or left out. Only the answers are ours. See the original question paper.
Duration 1 hours · Total marks 30 · 12 questions answered
How to use this volume
Solve the paper first, under exam conditions and against the clock. Then read the answers here and mark your own. Reading a solution before attempting the question feels productive and teaches very little, because recognising an answer is not the same as being able to write one.
SECTION I
Q1)
Attempt any two · 10 Marks
A)Explain uses of Automata.[5]
Answer
For full marks, cover: what an automaton is, the main kinds (finite automata, pushdown automata, Turing machines) with what each models, and the practical uses in compilers, text search, hardware design, networking and other areas, with examples.
What an automaton is
An automaton is an abstract model of a computing machine. It reads an input string symbol by symbol and changes its state by fixed rules. At the end it accepts or rejects the string, or it produces an output. The main kinds are:
- Finite automata (DFA, NFA), which have a fixed, finite memory, their states. They recognise regular languages.
- Pushdown automata (PDA), a finite automaton with a stack. They recognise context-free languages.
- Linear bounded automata, which recognise context-sensitive languages.
- Turing machines, with an unlimited tape. They model any computation a computer can do.
Uses of automata
- Compilers, lexical analysis. The lexical analyser (scanner) of a compiler is a finite automaton. It recognises tokens such as identifiers, keywords and numbers. Tools such as Lex build it from regular expressions.
- Compilers, parsing. The parser checks the program's syntax using a context-free grammar, and is a pushdown automaton. Tools such as Yacc build it.
- Text search and editors. Searching for patterns, as in grep, find-and-replace in editors, and form validation (email, phone number) uses regular expressions, run as finite automata.
- Digital circuit design. Sequential circuits such as counters, vending-machine controllers and traffic-light controllers are designed as finite state machines. Mealy and Moore machines are used directly here.
- Network protocols. Protocols such as TCP are described as state machines (listening, connected, closing), which helps design and verify them.
- Natural language processing. Automata and grammars are used in spell checkers, morphology and speech recognition.
- Games and user interfaces. Game characters and menu flows are modelled as state machines.
- Theory of computing. Turing machines define what can and cannot be computed (decidability, the halting problem), and lead to complexity classes such as P and NP.
Conclusion. Automata are abstract models of machines, from finite automata to Turing machines. They are used in compilers for lexical analysis and parsing, and in text search. They also help design digital circuits and protocols, process language, and decide what computers can and cannot do.
The rest of the answers
The first answer is free. The rest come with the B.Sc. (Computer Science) Semester 3 solved papers.
You have read the question paper and its first answer in full. Buy the solved papers once and you can read every answer of every solved paper in this semester.
Notes + practical solutions + solved papers: ₹798 Already bought it? Sign in
Or solved papers only: ₹499
Or notes + practical solutions: ₹499
The question paper itself stays free, and so does the syllabus.
Found an error in this volume? Report it and we will check it against the paper.