# 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

### View Answer

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

### View Answer

3. Linear grammar has more than one non-terminal on the right-hand side.

a) True

b) False

### View Answer

4. In Right-Linear grammars, all productions have the form: A → xB.

a) True

b) False

### View Answer

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

### View Answer

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

### View Answer

7. Which Grammar is it?

a) Right Linear

b) Left Linear

c) None of the mentioned

d) Both of the mentioned

### View Answer

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

### View Answer

9. A Regular Grammar is any right-linear or left-linear grammar.

a) True

b) False

### View Answer

10. Regular Grammars generate Regular Languages.

a) True

b) False

### View Answer

## Set 2

1. Can Left Linear grammar be converted to Right Linear grammar

a) Yes

b) No

### View Answer

2. CFG is

a) Compiler

b) A language expression

c) Regular Expression

d) None of the mentioned

### View Answer

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

### View Answer

4. Transition of finite automata is

a) Finite Diagram

b) State Diagram

c) Node Diagram

d) E-R Diagram

### View Answer

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

### View Answer

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

### View Answer

7. Which of the following identity is wrong?

a) R + R = R

b) (R*)* = R*

c) ɛR = Rɛ = R

d) ØR = RØ = RR*

### View Answer

8. Grammars that can be translated to DFAs

a) Left linear grammar

b) Right linear grammar

c) Generic grammar

d) All of the mentioned

### View Answer

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

### View Answer

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

### View Answer

## 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)

### View Answer

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)

### View Answer

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

### View Answer

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 *

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

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) 2^{n}

### View Answer

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

### View Answer

## 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

### View Answer

2. Recursive descent parsing is an example of

a) Top down parsing

b) Bottom up parsing

c) Predictive parsing

d) None of the mentioned

### View 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

### View Answer

4. Lr parser are attractive because

a) CFG acknowledged

b) It does not backtrack

c) Both of the mentioned

d) None of the mentioned

### View Answer

5. Which is the most powerful parser?

a) SLR

b) LALR

c) Canonical LR

d) Operator-precedence

### View Answer

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

### View Answer

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

### View Answer

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

### View Answer

9. When will the relationship between ‘<’ and ‘>’ be <

a)>

b)<

c)=

d)Undefined

### View Answer

## 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

### View Answer

2. E(q) is known ε-closure of q.

a) True

b) False

### View Answer

3. ε-transitions does not add any extra capacity of recognizing formal

a) True

b) False

### View Answer

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

### View Answer

5. The transitions which does not take an input symbol are called

a) ε-transitions

b) λ-transitions

c) ε-transitions & λ-transitions

d) None of the mentioned

### View Answer

6. A nondeterministic finite automaton with ε-moves is an extension of nondeterministic finite automaton

a) True

b) False

### View Answer

7. Is an ordinary NFA and a NFA-ε are equivalent

a) True

b) False

### View Answer

8. Which is a correct statement?

a) { If an bn | n = 0,1, 2, 3 ..} is regular language

b) Strings with equal number of a’s and b’s denies a regular language

c) L (A* B*)∩ B gives the set A

d) None of the mentioned