Theory Of Computation MCQ - Context free languages
1) Correct hierarchical relationship among context- free, right-linear, and context-sensitive language is
Option: D
2)In the following grammar :
x : : = x ⊕ y | 4
y : : = z * y I 2
z : : = id
which of the folowing is true ?
Option: A
3) Which of the following CFG's can't be simulated by an FSM ?
Option: B
4) ADG is said to be in Chomsky Form (CNF), if all the productions are of the form A --> BC or
A --> a. Let G be a CFG in CNF. To derive a string of terminals of length x , the number of productions to be used is
Option: A
5) Which of the following statements is correct?
Option: C
6) P, Q, R are three languages, if P and R are regular and if PQ = R, then
Option: C
7) A class of language that is closed under
Option: D
8) The productions
E—>E+E
E—>E—E
E-->E*E
E —> E / E
E —> id
Option: B
9) Which of the folowing definitions below generates the same language as L, where
L = {xn yn such that n > = 1} ?
I. E —> xEy | xy
II. xy | (x+ xyy+)
III .x+y+
Option: A
10) Following context free grammar
S —> aB | bA
A —>b | aS | bAA
B —> b | bS | aBB
generates strings of terminals that have
Option: A
11) Define for the context free language
L< {0;1} init (L) = { u | u v ε L for some v in {0, 1}}
If L { w | w is nonempty and has an equal number of 0's and 1's}, then init (L) is set of all binary strings
Option: B
12) Which of the following CFG's can't be simulated by an FSM ?
Option: C
13) Basic limitation of FSM is that it
Option: A
14)
Which of the following is not possible algorithmically ?
Option: C
15) The set {anbn | n = 1, 2, 3 ...} can be generated by the CFG
Option: D
16) The CFG
s---> as | bs | a | b
is equivalent to regular expression
Option: B
17) Consider the grammar :
S —> ABCc | Abc
BA —> AB
Bb —> bb
Ab —> ab
Aa —> aa
Which of the following sentences can be derived by this grammar
Option: A
18)
Pumping lemma is generally used for proving that
Option: B
19) The language of all words with at least 2 a's can be described by the regular expression
Option: D
20) Any string of terminals that can be generated by the following CFG is
S-> XY
X--> aX | bX | a
Y-> Ya | Yb | a
Option: D
21) L = (an bn an | n = 1,2,3) is an example of a language that is
Option: D
22) If Σ = (0, 1), L = Σ* and R = (0n 1nsuch that n > 0 )
then languages L ∪ R and R respectively are
Option: B
23) FSM can recognize
Option: D
24) Set of regular languages over a given alphabet set is closed under
Option: D
25) Which of the following statement is correct?
Option: D
26) Given A = (0,1) and L = A*. If R = (0n 1n, n > 0) , then language L ∪ R and R are respectively
Option: D
27) Define for a context free language
L ≤ {0 ; 1} init (L) = {u/uv ε L for some v in {0,1}}
(in other words, init (L) is the set of prefixes of L)
Let L {w/w is noempty and has an equal number of 0’s and 1’s)
Then init (L) is
Option: B
28) If L1 and L2 are context free language and R a regular set, then which one of the languages below is not necessarily a context free language?
Option: B
29) Consider a grammar with the following productions
S--> aab | bac | aB
S --> α S | b
S --> α b b | ab
Sα --> bdb | b
The above grammar is
Option: C
30) What can be said about a regular language L over {a} whose minimal finite state automation has two states?
Option: B
31) In a context-sensitive grammar, number of grammar symbols on the left hand side of a production can't be greater than the number of
Option: C
32) In a context-free grammar
Option: D
33) CFG can be recognized by a
Option: C
34) Which of the following statements are true?
I. The set of all odd integers is a monoid under multiplication.
II. The set of all complex number is a group under multiplication
III. The set of all integers under the operation * given by a * b = a+b-ab is a monoid
IV. Zs under symmetric difference defined by
A B = (A-B) ∪ (B-A) is an abelian group
Option: B
35) A given grammar is called ambiguous if
Option: C
36) Let L be a language recognizable by a finite automaton. The language
REVERSE (L) = {w such that w is the reverse of v where v ∈ L } is a
Option: A
37) The grammars G = ( { s }, { 0, 1 }, p , s)
where p = (s —> 0S1, S —> OS, S —> S1, S —>0} is a
Option: B
38) The logic of pumping lemma is a good example of
Option: A
39) The intersection of CFL and regular language
Option: B
40) For two regular languages
L1 = (a + b)* a and L2 = b (a + b ) *
,
the intersection of L1 and L2 is given by
Option: D
41) Context free grammar is not closed under
Option: C
42) If L be a language recognizable by a finite automaton, then language front
{L} = { w such that w is prefix of v where v ∈ L }, is a
Option: A
43) For which of the following application, regular expressions can not be used ?
Option: C
44) Consider the following grammar
S --> Ax / By
A --> By/Cw
B --> x / Bw
C--> y
Which of the regular expressions describe the same set of strings as the grammar ?
Option: A
45) Which of the following statements is (are) correct ?
Option: D
46) Which of the following statement is wrong ?
Option: D
47) Consider a grammar :
G = ( { x , y ) , { s , x , y } , p , s)
where elements of parse :
S--> x y
S -->y x
x--> x z
x--> x
y--> y
z--> z
The language L generated by G most accurately is called
Option: D
48) Consider a grammar :
G = { { S } , { 0 , 1 } , p , s }
where elements of p are:
S --> ss
S--> 0S1
S--> 1S0
S--> empty
The grammer will generate
Option: A
49) A grammar that produces more than one parse tree for some sentence is called
Option: A
50) Given a grammar G a production of G with a dot at some position of the right side is called
Option: A
51) If a language is denoted by a regular expression
L = ( x )* (x | y x ) ,
then which of the following is not a legal string within L ?
52) If every string of a language can be determined, whether it is legal or illegal in finite time, the language is called
Option: A
53) The defining language for developing a formalism in which language definitions can be stated, is called
Option: A
54) If L be set of strings from alphabet, then kleen closure of L is given as
Option: B
55) If e1 and e2 are the regular expressions denoting the languages L1 and L2 respectively, then which of the following is wrong ?
Option: C
56)
Context-free grammar can be recognized by
Option: D
57) he language L = (0n 1n 2n where n > 0) is a
Option: B
58) Context free language are closed under
Option: B
59) If G = ({S}, {a}, {S -> SS), S),
then language generated by G is
Option: A
60) Grammar
S —> a,
S —> A3A4 ,
A3 —> A1, A3, A2 ,
A3 —> A1 A2, A1
A2—> aA2A1 ,
A1a —> a A1,
A2a —> aA2,
A1A4 —> A4a,
A2A4 —> A5a,
A2A5 —> A5a,
A5 —> a
generates
Option: A
61) If L1 = {x | x is a palindrome in (0 + 1)*}
L2 = {letter (letter + digit)* };
L3 = (0n 1n 2n | n > 1}
L4 = {ambnam+n | m, n > 1}
then which of the following statement is correct ?
Option: A
62) A grammar to generate
{ (ab)n I n ≥ 1 } ∪ { (ba)n I n ≥ 1 }
is constructed as
Option: C
63) Consider the grammar
S ---> PQ | SQ | PS
P ---> x
Q--> y
To get a string of n terminals, the number of productions to be used is
Option: D
64) What is the highest type number which can be applied to the following grammar ?
S —> Aa, A —> Ba, B —> abc
Option: C
65) Following syntax-directed translation scheme is used with a shift reduction (bottom up) parser that perform the action in braces immediately after a reduction by the corresponding production
A —> aB {print “(1)” A —> c {print “1”),
B —> Ab {print *2”}.
When parser is aaacbbb, then string printed
Option: A
Theory Of Computation MCQ - Regular languages and finite automata
1) Number of states of the FSM required to simulate behaviour of a computer with a memory capable of storing "m" words, each of length 'n'
Option: B
2)
An FSM with
Option: C
3) If two finite states machine M and N are isomorphic, then
Option: A
4)
Power of
Option: D
5) Which of the folowing pairs of regular expressions are equivalent ?
Option: D
6)
A finite state machine with the following state table has a single input x and a single output z. If initial state is unknown, then shortest input sequence to reach the inal state C is
Option: B
7) An FSM can be used to add how many given integers ?
Option: D
8)
If two finite state machines are equivalent, they should have the same number of
Option: D
9) For which of the following applications regular expressions can be used ?
Option: D
10) L = {aP | p ; } is prime is
Option: B
11) In an incompletely specified automata
Option: D
12)
If f : {a, b}* —> (a, b}* be given by f (n) = ax for every value of n ∈ (a, b}, then f is
Option: A
13) The word 'formal' in formal languages means
Option: C
14) Running time of NFA to DFA conversion including the case where NFA has e-transition is
Option: C
15)
Which of the following statements is/are false ?
Option: D
16) Which of the following are not regular ?
Option: D
17) The main difference between a DFSA and an NDFSA is
Option: C
18) If w ∈ (a, b)* satisfy abw = wab, then (w) is
Option: A
19) A PDM behaves like an FSM wnen the number of auxiliary memory it has, is
Option: A
20) Finite state machine can recognize
Option: D
21) The major difference between a moore and mealy machine is that
Option: B
22) Any given transition graph has an equivalent
Option: D
23) For which of the following application, regular expressions cannot be used ?
Option: D
24) If S be an infinite set and be sets such that S1 ∪ S2 ∪ .....∪ SN = S, then
Option: C
25) Vienna Definition Language is an example of language definition facility based on
Option: A
26) Which of the following regular expressions denotes a language comprising all possible strings over the alphabet {a, b } ?
Option: B
27)
An FSM (Finite State Machine) can be considered to be a TM (Turing Machine) of finite tape length
Option: A
28) Palindromes can't be recognized by any FSM because
29) If ∑ = {a, b, c, d, e, f } then number of strings in ∑ of length 4 such that no symbol is used more than once in a string is
Option: B
30) A language L is accepted by a finite automaton if and only if it is
Option: D
31) Can a DFA simulate NFA?
Option: B
32) Which of the following statements is wrong ?
Option: C
33) Regular expression a / b denotes the set
Option: C
34) Regular expression (a | b ) (a | b) denotes the set
Option: D
35) Which of the following regular expressions denotes zero or more instances of an a or b ?
Option: C
36) Which of the following regular expressions denotes a language comprising all possible strings of even length over the alphabet ( 0 , 1 ) ?
Option: C
37) The regular expression (a | b)* denotes the set of all strings
Option: D
38) The string (a) | ((b) * (c)) is equivalent to
Option: C
39) An automation is a __________ device and a grammar is a __________ device.
Option: D
40) In the figure given below, a deterministic finite automation M has start state A and accepting state D. Which of the following regular expression denoted the set of all words accepted by M ?
Option: C
41) The regular sets are closed under
Option: D
42) Dynamic errors can be detected at
Option: B
43)
If a and b be the regular expressions, then ( a* ∪ b* ) * is equivalent to
Option: D
44) Finite state machines _________ recognize palindromes
Option: B
45) If S and T be language over Σ = {a, b } represented by regular expression (a + b * ) * and (a + b) * , respectively, then
Option: C
46) Consider regular expression (0 + 1) (0 + 1) ....... n times. Minimum state finite automaton that recognizes the language represented by this regular expression contains
Option: B
47) If regular set A is represented by A = (01 + 1)* and the regular set 'B' is represented by B = ((01)*1*)*, then
Option: D
48) Which of the following can be recognized by a Deterministic Finite-state Automaton ?
Option: A
49) Which of the following are not regular ?
Option: D
50) An FSM with
Option: C
51) If w ∈ (a, b)* satisfy abw = wab, then (w) is
Option: A
52) A PDM behaves like an FSM wnen the number of auxiliary memory it has, is
Option: A
53)
A finite state machine with the following state table has a single input x and a single output z
If the initial state is unknown, then shortest input sequence to reach the final state C is
1)Which of the following is complement of a?
2) If nL can be recognized by a multitape TM with time complexity f, then L can be recognized by a one-tape machine with time complexity DSD
3) If T is a TM recognizing L, and T reads every symbol in the input string, Ï„T(n) ≥ 2n + 2, then any language that can be accepted by a TM T with Ï„T(n) = 2n + 2 is
4) Consider an alternate Turing machine model, in which there is an input tape on which the tape head can move in both directions but cannot write, and one or more work tapes, one of which serves as an output tape. For a function f, denoted by DSpace ( f ) , the set of languages that can be recognized by a Turning machine of this type which uses no more than f(n) squares on any work tape for any input string of length n. The only restriction we need to make on f is that f(n) > 0 for every n. The language of balanced strings of parentheses are in
5) Which of the following problems is solvable ?
6) Which of the following is not primitive recursive but partially recursive ?
7)Turing machine (TM) is more powerful than FMS (Finite State Machine) because
8) If f : N--> N. If L can be recoognized by a TM T, so that Ï„T(n) ≤ f (n) for all but finitely many n, then ( Time (f) means Time ( max ( f, 2n +2))).
9) Let s is a step-counting function satisfying s(n) ≥ n, and L be a language accepted by a (multitape) TM T. If tape heads of T do not move past square s(n) on any of the tapes for an input string of length n, then T ∈
10) Which of the following statements is false ?
11) Bounded minimalization is a technique for
12) If there exists a language L, for which there exists a TM, T, that accepts every word in L and either rejects or loops for every word that is not in L, is called
13) Which of the following statement(s) is/are correct?
14) Universal TM influenced the concept of
15) Number of external states of a UTM should be atleast
16) The statement, “A TM can’t solve halting problem” is
17) If there exists a TM which when applied to any problem in the class, terminates, if correct answer is yes and may or may not terminate otherwise is called
18)Given a Turing machine T and a step-counting function f, is the language accepted by T in Time(f) ? This decision problem is
19) A total recursive function is a
20) The running time T (n), where 'n' is input size of a recursive algorithm, is given as
T (n) = c + T (n - 1), if n > 1
= d, if n ≤ 1
The order of the algorithm is
21) Next move function δ of a Turing machine M = (Q, Σ , Γ, δ, q0, B, F) is a mapping
22) If L can be recognized by a TM T with a doubly infinite tape, and Ï„t = f, then L can be recognized by an ordinary TM with time complexity
Thank you
Post a Comment