NEW
Font size
WorksheetsTheory of Computation
Total questions: 20
Worksheet time: 12mins
Correct hierarchical relationship among context- free, right-linear, and context-sensitive language is
context-free ⊂ right-linear ⊂ context-sensitive
context-free ⊂ context-sensitive ⊂ right-linear
context-sensitive ⊂ right-inear ⊂context-free
right-linear ⊂context-free ⊂context-sensitive
In the following grammar :
x : : = x ⊕ y | 4
y : : = z * y I 2
z : : = id
which of the following is true ?
⊕ is left associative while * is right associative
Both ⊕ and * are left associative
⊕ is right associative while * is left associative
None of these
Which of the following CFG's can't be simulated by an FSM ?
S --> Sa | b
S --> aSb | ab
S --> abX, X --> cY, Y --> d | aX
None of these
Which of the following statements is correct?
A = { If an bn | n = 0,1, 2, 3 ..} is regular language
Set B of all strings of equal number of a's and b's deines a regular language
L (A* B*)∩ B gives the set A
None of these
A class of language that is closed under
union and complementation has to be closed under intersection
intersection and complement has to be closed under union
union and intersection has to be closed under complementation
both (A) and (B)
The productions
E—>E+E
E—>E—E
E-->E*E
E —> E / E
E —> id
generate an inherently ambiguous language
generate an ambiguous language but not inherently so
are unambiguous
can generate all possible fixed length valid computation for carrying out addition, subtraction, multipication and division, which can be expressed in one expression
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+
I only
I and II
II and III
II only
Following context free grammar
S —> aB | bA
A —>b | aS | bAA
B —> b | bS | aBB
generates strings of terminals that have
equal number of a's and b's
odd number of a's and odd number b's
even number of a's and even number of b's
odd number of a's and even number of a's
The CFG
s---> as | bs | a | b
is equivalent to regular expression
(a + b)
(a + b) (a + b)*
C.(a + b) (a + b)
None of these
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
abc
aab
abcc
abbb
Pumping lemma is generally used for proving that
given grammar is regular
given grammar is not regular
whether two given regular expressions are equivalent or not
None of these
The language of all words with at least 2 a's can be described by the regular expression
(ab)*a and a (ba)*
(a + b)* ab* a (a + b)*
b* ab* a (a + b)*
all of these
Any string of terminals that can be generated by the following CFG is
S-> XY
X--> aX | bX | a
Y-> Ya | Yb | a
has atleast one 'b'
should end in a 'a'
has no consecutive a's or b's
has atleast two a's
If Σ = (0, 1), L = Σ* and R = (0n 1nsuch that n > 0 )
then languages L ∪ R and R respectively are
Regular, Regular
Regular, Not regular
Not regular, Not regular
None of these
Which of the following statement is correct?
All languages can not be generated by CFG
Any regular language has an equivalent CFG
Some non regular languages can't be generated by CFG
both (b) and (c)
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?
L1 L2
L1 ∩ L2
L1 ∩ R
L1 ∪ L2
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
Context free
regular
context sensitive
LR ( k )
A given grammar is called ambiguous if
two or more productions have the same non-terminal on the left hand side
a derivation tree has more than one associated sentence
there is a sentence with more than one derivation tree corresponding to it
brackets are not present in the grammar
The grammars G = ( { s }, { 0, 1 }, p , s)
where p = (s —> 0S1, S —> OS, S —> S1, S —>0} is a
recursively enumerable language
regular language
context-sensitive language
context-free language
The logic of pumping lemma is a good example of
pigeon-hole principle
divide-and-conquer technique
recursion
iteration
