A directory of Objective Type Questions covering all the Computer Science subjects. Here you can access and discuss Multiple choice questions and answers for various compitative exams and interviews.

11. Given the following statements:

S1: If L is a regular language then the language {uv | u ∈  L, v ∈ LR } is also regular.
S2: L = {wwR} is regular language.

Which of the following is true?
a. S1 is not correct and S2 is not correct
b. S1 is not correct and S2 is correct
c.  S 1 is correct and S2 is not correct
d. S1 is correct and S2 is correct
View Answer Report Discuss Too Difficult! Search Google
Answer: (d).S1 is correct and S2 is correct

12. Given the following statements.

S1: The grammars S → asb | bsa |ss I a and s→ asb | bsa| a are not equivalent.
S2: The grammars S→. ss| sss | asb | bsa| λ and S → ss |asb |bsa| λ are equivalent.

Which of the following is true?
a. Sl is correct anet S2 is not correct
b. Both S1 and S2 are correct
c. S1 is not Correct and S2 is correct
d. Both S1 and S2 are not correct
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).Both S1 and S2 are correct

13. Pumping -lemma for context-free languages states :
Let Lbe an infinite context free language. Then there exists some positive integer m such that any w ∈ L with Iwl ≥m can be decomposed as w = uv xy Z with Ivxyl_________ and Ivy I such that uvz, xyZ
Z ∈ L for all z = 0, 1,2, .......
a. ≤m, ≤1
b. ≤m,≥1
c. ≥m,≤1
d. ≥m, ≥1
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).≤m,≥1

14. The Greibach normal form grammar for the language L = {an bn+1 | n ≥ 0 } is
a. S →  aSB, B →bB I  λ
b. S →  aSB, B →bB I  b
c. S →  aSB I b, B→b
d. S →  aSB I b
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).S →  aSB I b, B→b

15. Given the following statements:

S1: Every context-sensitive language L is recursive.
S2: There exists a recursive language that is not context sensitive.

Which statement is correct?
a. S1 is not correct and S2 is not correct
b. S1 is not correct and S2 is correct
c. S1 is correct and S2 is not correct
d. S1 is correct and S2 is correct
View Answer Report Discuss Too Difficult! Search Google
Answer: (d).S1 is correct and S2 is correct

16. Shift-Reduce parsers perform the following :
a. Shift step that advances in the input stream by K(K > 1) symbols and Reduce step that applies a completed grammar rule to some recent parse trees, joining them together as one tree with a new root symbol.
b. Shift step that advances in the input stream by one symbol and Reduce step that applies a completed grammar rule to some recent parse trees, joining them together as one tree with a new root symbol.
c. Shift step that advances in the input stream by K(R = 2) symbols and Reduce step that applies a completed grammar rule to form a single tree.
d. Shift step that does not advance in the input stream and Reduce step that applies a completed grammar rule to form a single tree.
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).Shift step that advances in the input stream by one symbol and Reduce step that applies a completed grammar rule to some recent parse trees, joining them together as one tree with a new root symbol.

17. The following Context-Free Grammar (CFG) :

S → aB | bA

A → a | as | bAA

B → b | bs | aBB

will generate
a. odd numbers of a's and odd numbers of b's
b. even numbers of a's and even numbers of b's
c. equal numbers of a's and b's
d. different numbers of a's and b's
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).equal numbers of a's and b's

18. Which of the following is true?
a. Canonical LR parser is LR (1) parser with single look ahead terminal
b. All LR(K) parsers with K > 1 can be transformed into LR( 1) parsers
c. Both a and b
d. None of the above
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).Both a and b

19. The pushdown automation M = ( {q0, q1, q2}',{a, b}, {0, 1}, δ, q0,0, {q0}) with

δ (q0, a, 0) = {(q1,10)}

δ (q1,a, 1) = {(q1,11)}

δ (q1,b, 1) = {(q2 , λ)}

δ(q2 , b, 1) = {(q2 , λ)}

δ (q2 , A, 0) = {(q0, λ)}

Accepts the language
a. L= {a^nb^m l n,m >=0}
b. L= {a^nb^n l n >=0}
c. L= {a^nb^m l n,m >0}
d. L= {a^nb^n l n >0}
View Answer Report Discuss Too Difficult! Search Google
Answer: (a).L= {a^nb^m l n,m >=0}

20. Given two languages:

L1= {(ab)n,ak I n> k, k >=0}

L2 = {an bm l n ≠ m}

Using pumping lemma for regular language, it can be shown that
a. L1 is regular and L2 is not regular
b. L1 is not regular and L2 is regular
c. L1 is regular and L2 is regular
d. L1 is not regular and L2 is not regular
View Answer Report Discuss Too Difficult! Search Google
Answer: (a).L1 is regular and L2 is not regular

Page 2 of 13