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.

1. Given the following expressions of a grammar

E --> E * F / F + E / F
F --> F - F / id

Which of the following is true ?
a. * has higher precedence than +
b. - has higher precedence than *
c. + and  - have same precedence
d. + has higher precedence than *
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).- has higher precedence than *

2. Which of the following is true while converting CFG to LL(1) grammar ?
a. Remove left recursion alone
b. Factoring grammar alone
c. Both of the above
d. None of the above
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).Both of the above

3. Let L be a set accepted by a non deterministic finite automaton. The number of states in non-deterministic finite automaton is |Q|. The maximum number of states in equivalent finite automaton that accepts L is
a. |Q|
b. 2|Q|
c. 2^|Q| – 1
d. 2^|Q|
View Answer Report Discuss Too Difficult! Search Google
Answer: (d).2^|Q|

4. The grammar ‘G1’

S ---> OSO| ISI | 0|1|∈

and the grammar  ‘G2’ is
S ---> as |asb| X,
X -----> Xa | a.

Which is the correct statement ?
a. G1 is ambiguous, G2 is unambiguous
b. G1 is unambiguous, G2 is ambiguous
c. Both G1 and G2 are ambiguous
d. Both G1 and G2 are unambiguous
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).G1 is unambiguous, G2 is ambiguous

5. Which of the following regular expression identities are true ?
a. (r + s)* = r* s*
b. (r + s)* = r* + s*
c. (r + s)* = (r*s*)*
d. r* s* = r* + s*
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).(r + s)* = (r*s*)*

6. The minimum number of states of the non-deterministic finite automation which accepts the language
{a b a bn| n  ≥  0} ∪ {a b an|n  ≥ 0} is 
a. 3
b. 4
c. 5
d. 6
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).5

7. Which of the following definitions generates the same Language as L, where
L = {WWR | W ∈ {a, b}*} 
a. S ∈ asb|bsa|∈
b. S ∈ asa|bsb|∈
c. S ∈ asb|bsa|asa|bsb|∈
d. S ∈ asb|bsa|asa|bsb
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).S ∈ asa|bsb|∈

8. If the parse tree of a word w generated by a Chomsky normal form grammar has no path of length greater than i, then the word w is of length 
a. no greater than 2^(i+1) 
b. no greater than 2^i
c. no greater than 2^(i–1)
d. no greater than i
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).no greater than 2^(i–1)

9. Given the following statements :

S1: SLR uses follow information to guide reductions.In case of LR and LALR parsers, the look-aheads are associated with the  Items and they make use of the left context available to the parser.
S2: LR grammar is a larger sub-class of context free grammar as compared to that SLR and LALR grammars. 

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. S1 is correct and S2 is not correct
d. SI is correct and S2 is correct
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).S1 is correct and S2 is not correct

10. The context free grammar for the language

L= {anbm  | n ≤ m+3,n ≥ 0 ,m≥ 0 } : is
a. S → aaa; A → aAb | B, B →  Bb |  λ 
b. S → aaaA | λ ; A → aAb | B; B →  Bb |  λ ;
c. S → aaaA | aaA | λ ; A → aAb | B; ​B →  Bb |  λ ;
d. S → aaaA | aaA | aA |  λ ; A → aAb | B; ​B →  Bb |  λ ;
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).S → aaaA | aaA | λ ; A → aAb | B; ​B →  Bb |  λ ;

Page 1 of 13