Important theory of computation questions and answers which covers automata theory, regular expressions and regular languages, context free grammars and machine related topics.
|
Q 31.
Push down machine represents ?
Ans.
type - 2 grammer
|
|
Q 32.
What is the most general phase of structured grammer ?
Ans.
Context-sensitive
|
|
Q 33.
A FSM can be used to add how many given integers ?
Ans.
3
|
|
Q 34.
The ability for a system of instructions to simulate a Turing Machine is called ?
Ans.
Turing Completeness
|
|
Q 35.
What is the basic limitation of a FSM ?
Ans.
It cannot remember arbitrary large amount of information.
|
|
Q 36.
The language accepted by finite automata is called ?
Ans.
Regular
|
|
Q 37.
Context free languages are not closed under ?
Ans.
Iteration
|
|
Q 38.
The logic of pumping lemma is a good example of ?
Ans.
Pigeon-hole principle
|
|
Q 39.
Which is not primitive recursive but partially recursive ?
Ans.
Ackermann's function
|
|
Q 40.
Why Palindromes cannot be recognized by any FSM ?
Ans.
Because an FSM cannot deterministically fix the mid-point
|
|
Q 41.
A push down automata is different than finite automata by ?
Ans.
Its memory
|
|
Q 42.
Which regular expressions represents the set of strings which
do not contain a substring ‘rt’ if alphabet = {r, t} ?
Ans.
(tr)
|
|
Q 43.
What are Recursive languages ?
Ans.
A proper superset of CFL
|
|
Q 44.
The set of all strings over the alphabet S = {a, b} (including e) is denoted by ?
Ans.
(a + b)*
|
|
Q 45.
What is Deterministic Finite Automata (DFA) ?
Ans.
In DFA, for each input symbol, one can determine the state to which the machine will move.
|
|
Q 46.
What is the use of Grammer in TOC ?
Ans.
It is standard way of representing a language. It tell us that perticular string is the part of the given language or not.
A grammer 'G' is defined a quadrable G = {V, T, P, S} Here V is variable, T is terminal, P is production rule and S is start symbol |
|
Q 47.
Is identity element can exist in positive closure ( ∑+ ) ?
Ans.
No
|
|
Q 48.
What is Positive closure ?
Ans.
Positive closure is the infinite set of all possible strings of all possible lengths excluding Ɛ. It is denoted by ∑+. We can say like this ∑+=∑* - { Ɛ }
|
|
Q 49.
What is Kleene closure in TOC ?
Ans.
Kleene closure is the infinite set of all possible strings of all possible lengths including Ɛ or λ.
It is denoted by ∑* For ex:- If ∑ = {a, b}, ∑* = {λ, a, b, aa, ab, ba, bb,………..} |
|
Q 50.
How to calculate the Power of ∑ ( Sigma ) ?
Ans.
It is based on the set of all strings in Language. For ex:-
∑0 = Set of all strings in Length 0 ∑1 = Set of all strings in Length 1. ∑n = Set of all strings in Length n. |
|
Q 51.
What are the types of Automata ?
Ans.
In TOC we have 4 types of Automata.
1) FA ( Finite automata ) 2) PDA ( Push down automata ) 3) LBA ( Linear bound automata) 4) TM ( Turing machine) |
|
Q 52.
What is Automata theory ?
Ans.
In simple words, it is like a model or machine, which is used to find the given string is the part of the language or not. Means we use automata theory to check single string part exist or not in given langauge.
|
|
Q 53.
If a given alphabet is ∑ = {a, b} then find the language L1 where string of length is 3 ?
Ans.
Here we can make total 8 combination of strings using length 3.
Like: {aaa, aab, aba, abb, baa, bab, bba, bbb} So length L1 = 8 |
|
Q 54.
What is string in theory of computation ?
Ans.
A string is a finite sequence of alphabets. For example for alphabet ∑ = {a, b}, then w = a, b, aa, bb are strings.
|
|
Q 55.
What is language in TOC ?
Ans.
It is collection of all possible strings and can be finite or infinite.
|