Select Page
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages
Filter by Categories
nmims post
Objective Type Set
Online MCQ Assignment
Question Solution
Solved Question
Uncategorized

# Multiple choice question for engineering

## Set 1

1. Non-Linear grammar has has two non-terminals on the right-hand side.
a) True
b) False

Answer: a [Reason:] The above stated grammar is non-linear because it has two non-terminals on the right-hand side.

2. S → SS S → λ S → aSb S → bSa which type of grammar is it?
a) Linear
b) Nonlinear
c) Both of the mentioned
d) None of the mentioned

Answer: a [Reason:] Grammar is non-linear because one of the rules (the first one) has two non-terminals on the right-hand side.

3. Linear grammar has more than one non-terminal on the right-hand side.
a) True
b) False

Answer: a [Reason:] Grammar is linear because no rule has more than one non terminal on the right-hand side.

4. In Right-Linear grammars, all productions have the form: A → xB.
a) True
b) False

Answer: a [Reason:] Right-Linear grammars, following are the form of productions: A → xB or A → x where x is some string of terminals.

5. S → abS S → a is which grammar
a) Right Linear Grammar
b) Left Linear Grammar
c) Both of the mentioned
d) None of the mentioned

Answer: a [Reason:] Grammars in which all of the rules contain only one non-terminal on the left-hand side, and where in every case that non-terminal is the first symbol are called right Linear.

6. What are the two types of Linear Grammar?
a) Right Linear
b) Left Linear
c) None of the mentioned
d) Both of the mentioned

Answer: d [Reason:] Linear grammar is of 2 types Left and Right Linear Grammar.

7. Which Grammar is it?
a) Right Linear
b) Left Linear
c) None of the mentioned
d) Both of the mentioned

Answer: b [Reason:] In Left-Linear grammars, all productions have the form: A→Bx or A→ x where x is some string of terminals.

8. Which Type of Grammar is it?
S → Aa A → Aab | λ
a) Right Linear
b) Left Linear
c) None of the mentioned
d) Both of the mentioned

Answer: b [Reason:] In this case they both correspond to the regular expression (ab)*a.

9. A Regular Grammar is any right-linear or left-linear grammar.
a) True
b) False

Answer: a [Reason:] As it turns out the languages that can be generated by Regular Grammars is equivalent to those that can be specified by Regular Expressions.

10. Regular Grammars generate Regular Languages.
a) True
b) False

Answer: a [Reason:] That’s why tey are called regular languages.

## Set 2

1. Can Left Linear grammar be converted to Right Linear grammar
a) Yes
b) No

Answer: a [Reason:] Since right-linear grammars are regular, it follows that left-linear grammars are also regular.

2. CFG is
a) Compiler
b) A language expression
c) Regular Expression
d) None of the mentioned

Answer: b [Reason:] They are defined by rule A->b where A is non terminal and b is terminal.

3. The idea of an automation with a stack as auxiliary storage
a) Finite automata
b) Push Down Automata
c) Deterministic Automata
d) None of the mentioned

Answer: b [Reason:] Push Down Automata manipulate the Stack as a part of performing a transition.

4. Transition of finite automata is
a) Finite Diagram
b) State Diagram
c) Node Diagram
d) E-R Diagram

Answer: b [Reason:] Transition of finite automata is Finite Diagram.

5. A context free language is called ambiguous if
a) It has 2 or more than 2 left derivations for some terminal string ѡ є L (G)
b) It has 2 or more than 2 left derivations for some terminal string ѡ є L (G)
c) Both (a) and (b)
d) None of the mentioned

Answer: c [Reason:] When two or more Left and right most derivative occur the grammar turn ambiguous.

6. Which of the following statement is true?
a) Every language that is defined by regular expression can also be defined by finite automata
b) Every language defined by finite automata can also be defined by regular expression
c) We can convert regular expressions into finite automata
d) All of the mentioned

Answer: d [Reason:] All these statements are true w.r.t regular expression.

7. Which of the following identity is wrong?
a) R + R = R
b) (R*)* = R*
c) ɛR = Rɛ = R
d) ØR = RØ = RR*

Answer: d [Reason:] Regular grammar combined with empty does not give R* instead gives empty.

8. Grammars that can be translated to DFAs
a) Left linear grammar
b) Right linear grammar
c) Generic grammar
d) All of the mentioned

Answer: b [Reason:] Right Linear grammar can be translate to DFA.

9. A language is regular if and only if it is accepted by finite automata
a) The given statement statement is true
b) Given statement is false
c) Statement is partially true
d) None of the mentioned

Answer: a [Reason:] Regular Language is accepted by Finite Automata. Every regular language is Context free.

10. A Push Down Automata is if there is at most one transition applicable to each configuration
a) Deterministic
b) Non deterministic
c) Finite
d) Non finite

Answer: a [Reason:] In every situation only one transition is available as continuation then the result is deterministic push down automata.

## Set 3

1. S → C C
C → c C | d
The grammar is
a) LL(1)
b) SLR(1) but not LL(1)
c) LALR(1) but not SLR(1)
d) LR(1) but not LALR(1)

Answer: a [Reason:] Since there is no conflict, the grammar is LL (1) hence a predictive parse table with no conflicts can be constructed.

2. Which of the following statements is false?
a) Unambiguous grammar has both kind of derivations
b) An LL(1) parser is a top-down parser
c) LALR is more powerful than SLR
d) Ambiguous grammar can’t be LR(k)

Answer: a [Reason:] If a grammar has more than one leftmost (or rightmost) derivation the grammar is ambiguous.

3. Which of the following derivations does a top-down parser use while parsing an input string?
a) Leftmost derivation
b) Leftmost derivation in reverse
c) Rightmost derivation
d) Rightmost derivation in reverse

Answer: a [Reason:] Left to right constructing leftmost derivation of the sentence.

4. Given the following expression 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 *

Answer: b [Reason:] e.g. input is 3*4-5 r

```         E
/  |
E   *   F
|      / |
F      F - F
|     |    |
id(3) id(4) id(5)
```

First ‘- ‘ is be evaluated then ‘ *’.

5. Which one of the following is true at any valid state in shift-reduce parsing?
a) At the bottom we find the prefixes.
b) None of the mentioned
c) Stack contains only viable prefixes
d) Stack consists of viable prefixes

Answer: c [Reason:] The prefixes on the stack of a shift-reduce parser are called viable prefixes.

6. In the context of abstract-syntax-tree and control-flow-graph.
Which one of the following is true?
a) In both AST and CFG if node N2 be the successor of node N1.
b) For any input program, neither AST nor CFG will contain a cycle
c) The max no. of successors of a node in an AST and a CFG depends on the input program
d) None of the mentioned

Answer: c [Reason:] Successors depends on input.

7. Match the following:

```  List-I                  List-II
A. Lexical analysis       1. Graph colouring
B. Parsing                2. DFA minimization
C. Register allocation    3. Post-order traversal
D. Expression evaluation 4. Production tree```

A B C D
(a) 2 3 1 4
(b) 2 1 4 3
(c) 2 4 1 3
(d) 2 3 4 1

Answer: c [Reason:] The entire column an items matches the Column B items in a certain way.

7. Which of the following pairs is the most powerful?
a) SLR, LALR
b) Canonical LR ,LALR
c) SLR canonical LR
d) LALR canonical LR

Answer: c [Reason:] Parser algorithm is simple.

8. Consider the following grammar G.

``` S → F ⎪ H
F → p ⎪ c
H → d ⎪ c```

Which one is true?
S1: All strings generated by G can be parsed with help of LL (1).
S2: All strings generated by G can be parsed with help of LR (1).
a) Only S1
b) Only S2
c) Both S1 S2
d) None of the mentioned

Answer: d [Reason:] There is ambiguity as the string can be derived in 2 possible ways. First Leftmost Derivation S → F F → c Second Leftmost Derivation S → H H → c .

9. What is the maximum number of reduce moves that can be taken by a bottom-up parser for a grammar with no epsilon- and unit-production to parse a string with n tokens?
a) n/2
b) n-1
c) 2n-1
d) 2n

Answer: b [Reason:] The moves are n-1.

10. Consider the following two sets of LR (1) items of an LR (1) grammar.

```  X -> c.X, c/d
X -> .cX, c/d
X -> .d, c/d
X -> c.X, \$
X -> .cX, \$
X -> .d, \$```

Which one is false?
1. Cannot be merged since look ahead’s are different.
2. Can be merged but will result in S-R conflict.
3. Can be merged but will result in R-R conflict.
4. Cannot be merged since goto on c will lead to two different sets.
a) 1 only
b) 2 only
c) 1 and 4 only
d) 1, 2, 3 and 4 only

Answer: d [Reason:] All these are valid reasons.

## Set 4

1. The grammar S → aSa | bS | c is
a) LL(1) but not LR(1)
b) LR(1) but not LR(1)
c) Both of the mentioned
d) None of the mentioned

Answer: c [Reason:] First(aSa) = a First(bS) = b First(c) = c LR parsers are more powerful than LL (1) parsers and LR (1).

2. Recursive descent parsing is an example of
a) Top down parsing
b) Bottom up parsing
c) Predictive parsing
d) None of the mentioned

Answer: a [Reason:] Top down is the answer.

3. LR stands for
a) Left to right
b) Left to right reduction
c) Right to left
d) Right most derivation and Left to right and a in reverse

Answer: d [Reason:] Right most derivation and left to right and in reverse is used for LR.

4. Lr parser are attractive because
a) CFG acknowledged
b) It does not backtrack
c) Both of the mentioned
d) None of the mentioned

Answer: c [Reason:] It is attractive because of these reasons.

5. Which is the most powerful parser?
a) SLR
b) LALR
c) Canonical LR
d) Operator-precedence

Answer: c [Reason:] Canonical tops all other parsers.

6. Choose the correct statement
a) CFG is not LR
b) Ambiguous Grammar can never be LR
c) Both of the mentioned
d) None of the mentioned

Answer: c [Reason:] Mentioned reason is true.

7. How is the parsing precedence relations defined
a) None of the mentioned
b) All of the mentioned
c) To delimit the handle
d) Only for a certain pair of terminals

Answer: b [Reason:] The reason why the precedence operations is performed.

8. When will the relationship between ‘+’ and ‘-’ be <
a) For unary minus
b) Minus is right associative
c) All of the mentioned
d) None of the mentioned

Answer: c [Reason:] Both statements are true.

9. When will the relationship between ‘<’ and ‘>’ be <
a)>
b)<
c)=
d)Undefined

Answer: d [Reason:] Undefined. There is no existing relationship between the two.

## Set 5

1. NFA-εs are defined because certain properties can be more easily proved on them as compared to NFA.
a) True
b) False

Answer: a [Reason:] NFA-ε can be transformed into a NFA always, the properties are also true for NFAs.

2. E(q) is known ε-closure of q.
a) True
b) False

Answer: a [Reason:] The ε-closure of a set of states Z of an NFA is defined as the set of states reachable from any state in Z following ε-transitions.

3. ε-transitions does not add any extra capacity of recognizing formal
a) True
b) False

Answer: a [Reason:] ε-transitions provides a convenient transition in the systems whose current states are not precisely known.

4. Which of the following CFG’s can’t be simulated by an FSM ?
a) S->Sa/b
b) S->aSb/ab
c) S->abX, X->cY, Y->d/aX
d) None of the mentioned

Answer: b [Reason:] generates the set {an bn, n=1,2,3 ….}which is not regular ?.

5. The transitions which does not take an input symbol are called
a) ε-transitions
b) λ-transitions
c) ε-transitions & λ-transitions
d) None of the mentioned

Answer: c [Reason:] The transitions taking an input symbol are called ε-transitions or λ-transitions.

6. A nondeterministic finite automaton with ε-moves is an extension of nondeterministic finite automaton
a) True
b) False

Answer: a [Reason:] Both are equivalent.

7. Is an ordinary NFA and a NFA-ε are equivalent
a) True
b) False