Important theory of computation questions and answers which covers automata theory, regular expressions and regular languages, context free grammars and machine related topics.
|
Q 1.
If every string of a language can be determined, whether it is legal or illegal in finite time, the language is called ?
Ans.
Decidable
|
|
Q 2.
P, Q, R are three languages, if P and R are regular and if PQ = R, then ?
Ans.
Q need not be regular
|
|
Q 3.
If there exists a TM which when applied to any problem in the class, terminates if the correct answer is yes, and may not terminate otherwise is said to be ?
Ans.
Partially solvable
|
|
Q 4.
A given grammar is called ambiguous if ?
Ans.
There is a sentence with more than one derivation tree corresponding to it.
|
|
Q 5.
Context free language are closed under ?
Ans.
Union and Kleene closure
|
|
Q 6.
The language L generated by G most accurately is called ?
Ans.
Chomsky type 3
|
|
Q 7.
Bounded minimalization technique is used for ?
Ans.
To generate primitive recursive functions
|
|
Q 8.
How context-sensitive grammar (CSG) can be recognize ?
Ans.
By linearly bounded memory machine
|
|
Q 9.
Which is accepted by an NDPDM, but not by a DPDM ?
Ans.
Even Palindromes
|
|
Q 10.
A push down automata (PDM) behaves like a Turing machine, when the number of auxilary memory it has is ?
Ans.
2 or more
|
|
Q 11.
The defining language for developing a formalism in which language definitions can be stated, is called ?
Ans.
Syntactic meta language
|
|
Q 12.
The concept of FSA is much used in this part of the compiler ?
Ans.
Lexical analysis
|
|
Q 13.
Consider the following language, L = {anbmcpdq|n, m, p, q = 1}. Here L is ?
Ans.
Regular
|
|
Q 14.
The intersection of a context free language and a regular language is ?
Ans.
Always regular and context free
|
|
Q 15.
CFG is not closed under ?
Ans.
Complementation
|
|
Q 16.
Turing machine is more powerful than FSM because ?
Ans.
It has capability to remember arbitrary long sequences of input symbols.
|
|
Q 17.
R1 and R2 are regular sets. Which of the following is not true ?
Ans.
R1 n R2 need not be regular
|
|
Q 18.
A grammar that produces more than one parse tree for some sentence is called ?
Ans.
Ambiguous
|
|
Q 19.
Pumping lemma is generally used for proving ?
Ans.
A given grammer is not regular
|
|
Q 20.
Finite state automata (FSM) can only recognize ?
Ans.
Regular grammer
|
|
Q 21.
What is the recognizing capability of NDFSM and DFSM ?
Ans.
It is same
|
|
Q 22.
In which automata, we can do transition without any given input ?
Ans.
Epsilon NFA
|
|
Q 23.
Which machine is faster in between Moore and Mealy ?
Ans.
Mealy machine is more faster
|
|
Q 24.
In which machine Output is synchronous with clock ?
Ans.
Moore machine
|
|
Q 25.
In Mealy machine, if we give input of n length, then output will come as ?
Ans.
n length
|
|
Q 26.
In Moore machine, if we give input of n length, then output will come as ?
Ans.
n+1
|
|
Q 27.
What are the limitation of FSA ?
Ans.
Limited memory
Strings without comosition Linear power |
|
Q 28.
In DFA, null move is allow or not ?
Ans.
Null move allows in it.
|
|
Q 29.
What is NFA ( non deterministic automata ) ?
Ans.
In this we have multiple choices to move for one input symbol.
|
|
Q 30.
A language L is accepted by a FSA if it is ?
Ans.
Regular
|