Name of the College : Noorul Islam College of Engineering
University : Anna University
Degree : M.Sc
Department : Software Engineering
Subject Code/Name : XCS 352 – Theory of Computation
Year : 3rd
Semester : 5th
Document Type : Question Bank
Website : niceindia.com
Download Model/Sample Question Paper : https://www.pdfquestion.in/uploads/niceindia.com/3142-XCS_352__Theory_of_Computation.pdf
Theory of Computation Question Paper
1. Give the applications of Theory of computation :
a. Compiler Design
b. Robotics
c. Artificial Intelligence
d. Knowledge Engineering
Related : Noorul Islam College of Engineering XCS593 Networks Security M.Sc Question Bank : www.pdfquestion.in/3136.html
2. Give any four applications of Finite Automata :
a. It is an useful tool in the design of Lexical analyzer
b. Compiler design
c. Pattern matching
d. File Searching Program
3. Differentiate DFA with NFA :
A DFA is a deterministic Finite Automata where as NFA is a nondeterministic finite automata. In DFA, for a given state on a given input we reach to a deterministic and unique state. On the other hand, in NFA we may lead to more than one states for given input. The DFA is a subset of NFA.
4. Is it true the language accepted by NFA is different from the regular language? : Justify your answer:
No, it is false. For every regular expression r there exists a NFA with -transition that accepts L(r).
5. From the given automata, M, Check whether the string ababba is accepted or not :
The string is not accepted by given automata.
6. Is it true that the language accepted by a PDA by empty stock or that of final states are different in language? ::
No, because the languages accepted by PDA’s by final state are exactly the languages accepted by PDA’s by empty stack.
7. What is the additional feature of PDA has when compared with NFA? : Is PDA superior over NFA?: Is PDA superior over NFA in the sense of language acceptance?: Justify your answer:
Additional features of PDA :
a) PDA is eventually a FA with a stack.
b) PDA can accept context free languages.
c) PDA can recognize the context free languages which are not regular.
Yes, PDA is superior over NFA in the sense of languages.
8. Is it true the nondeterministic PDA is more powerful than that of deterministic PDA? : justify your answer:
Yes, wwR is accepted by NPDA but not any DPDA in the sense of language acceptance.
9. Regular Language :
A Language can be described by DFA or NFA. Context free language cannot be described by DFA (or) NFA – since there is no memory.
Pushdown Automata has a memory, which can be used to count the number. Pushdown Automata can accept context free languages. It is essentially an NFA with a stack.
10. Definition :
A language L is said to be deterministic context free language, if and only if there exists a deterministic pushdown automata (dpda) M such that L = L (M)
11. What are the actions takes place in Turning Machine :
In one move the turning machine, depending upon the symbol scanned by the tape head and the state of finite control,
1. Changes state
2. Prints a symbol on the tape cell scanned, replacing what was written there Moves its head left (or) right one cell.
12. Representation of turning machines :
We can describe Turing machine using
a. Instantaneous Descriptions
b. Transition table
c. Transition diagram
13. Define Multitape Turing Machine :
A multitape TM consists of a finite content with k tapes heads and k tapes, each tape, is infinite in both directions. On a single move, depending on the state of the finitecontrol and the symbol scanned by each of the tape heads. The machine can
a. Change state
b. Print a new symbol on each of the cells scanned by its tape head.
c. Move each of its tape heads, independently, one cell to the right or left or keep it stationary.
14. Is Tm is more powerful than FMs. :
Yes, Turing machine is more powerful than finite state machine because it has the capability to remember arbitarary relay long sequences of input symbol.
15. When a language is said to be recursive or recursively enumerable? ::
A language L is Recursive (R) if and only if there is a TM that decides L. L is Recursively enumerable (RE) if and only if there is a TM that semi decides L.
16. When a problem is said to be undesirable? ::
Curve an example of a decidable problem. A problem is undesirable if there is no algorithm that takes as input an instance of the problem and determines whether the answer to that instance, is yes or no.
Example for decidable problem Curve two DFSM M1 & M2, L (M1) = L (M2)