# Multiple choice question for engineering

## Set 1

1. CFGs are more powerful than:

a) DFA

b) NDFA

c) Mealy Machine

d) All of the mentioned

### View Answer

2. State true or false:

S-> 0S1|01

Statement: No regular expression exists for the given grammar.

a) true

b) false

### View Answer

^{n}1

^{n}|n>=1} which is not regular. Thus, no regular expression exists for the same.

3. For the given set of code, the grammar representing real numbers in Pascal has error in one of the six lines. Fetch the error.

(1)

(2)

(3)

(4)

(5)

(6)

a) 3

b) 4

c) 2

d) No errors

### View Answer

4. Which among the following is incorrect with reference to a derivation tree?

a) Every vertex has a label which is a terminal or a variable.

b) The root has a label which can be a terminal.

c) The label of the internal vertex is a variable.

d) None of the mentioned

### View Answer

5. Let G=(V, T, P, S)

where a production can be written as:

S->aAS|a

A->SbA|ba|SS

Which of the following string is produced by the grammar?

a) aabbaab

b) aabbaa

c) baabab

d) None of the mentioned

### View Answer

6. Statement 1: Ambiguity is the property of grammar but not the language.

Statement 2: Same language can have more than one grammar.

Which of the following options are correct with respect to the given statements?

a) Statement 1 is true but statement 2 is false

b) Statement 1 is false but statement 2 is true

c) Both the statements are true

d) Both the statements are false

### View Answer

7. Which of the following are non essential while simplifying a grammar?

a) Removal of useless symbols

b) Removal of unit productions

c) Removal of null production

d) None of the mentioned

### View Answer

8. Which of the following are context free language?

a) L={a^{i}b^{i}|i>=0}

b) L={ww^{r}| w is a string and r represents reverse}

c) Both (a) and (b)

d) one of the mentioned

### View Answer

9. The language L ={a^{i}2b^{i}|i>=0} is:

a) recursive

b) deterministic CFL

c) regular

d) Two of the mentioned is correct

### View Answer

10. L->rLt|tLr|t|r

The given grammar produces a language which is:

a) All palindrome

b) All even palindromes

c) All odd palindromes

d) Strings with same begin and end symbols

### View Answer

## Set 2

1. Context free grammar is called Type 2 grammar because of ______________ hierarchy.

a) Greibach

b) Backus

c) Chomsky

d) None of the mentioned

### View Answer

2. a→b

Restriction: Length of b must be atleast as much length of a.

Which of the following is correct for the given assertion?

a) Greibach Normal form

b) Context Sensitive Language

c) Chomsky Normal form

d) Recursively Ennumerable language

### View Answer

3. From the definition of context free grammars,

G=(V, T, P, S)

What is the solution of VÇT?

a) Null

b) Not Null

c) Cannot be determined, depends on the language

d) None of the mentioned

### View Answer

4. If P is the production, for the given statement, state true or false.

P: V->(V∑T)* represents that the left hand side production rule has no right or left context.

a) true

b) false

### View Answer

5. There exists a Context free grammar such that:

X->aX

Which among the following is correct with respect to the given assertion?

a) Left Recursive Grammar

b) Right Recursive Grammar

c) Non Recursive Grammar

d) None of the mentioned

### View Answer

6. If the partial derivation tree contains the root as the starting variable, the form is known as:

a) Chomsky hierarchy

b) Sentential form

c) Root form

d) None of the mentioned

### View Answer

7. Find a regular expression for a grammar which generates a language which states :

L contains a set of strings starting wth an a and ending with a b, with something in the middle.

a) a(a*Ub*)b

b) a*(aUb)b*

c) a(a*b*)b

d) None of the mentioned

### View Answer

8. Which of the following is the correct representation of grammar for the given regular expression?

a(aUb)*b

a) (1) S → aMb

(2) M → e

(3) M → aM

(4) M → bM

b) (1) S → aMb

(2) M → Mab

(3) M → aM

(4) M → bM

c) (1) S → aMb

(2) M → e

(3) M → aMb

(4) M → bMa

d) None of the mentioned

### View Answer

9. A CFG consist of the following elements:

a) a set of terminal symbols

b) a set of non terminal symbols

c) a set of productions

d) all of the mentioned

### View Answer

10. A CFG for a program describing strings of letters with the word “main” somewhere in the string:

a)

b)

c)

d) None of the mentioned

### View Answer

## Set 3

1. The use of variable dependency graph is in:

a) Removal of useless variables

b) Removal of null productions

c) Removal of unit productions

d) None of the mentioned

### View Answer

2. The variable which produces an epsilon is called:

a) empty variable

b) nullable

c) terminal

d) all of the mentioned

### View Answer

3. Statement:

For A-> e ,A can be erased. So whenever it appears on the left side of a production, replace with another production without the A.

State true or false:

a) true

b) false

### View Answer

4. Simplify the given grammar:

S->aXb

X->aXb | e

a) S->aXb | ab, X-> aXb | ab

b) S->X | ab, X-> aXb | ab

c) S->aXb | ab, X-> S | ab

d) None of the mentioned

### View Answer

5. Consider the following grammar:

A->e

B->aAbC

B->bAbA

A->bB

The number of productions added on the removal of the nullable in the given grammar:

a) 3

b) 4

c) 2

d) 0

### View Answer

6. Let G=(V, T, P, S) be a CFG such that _____________. Then there exists an equivalent grammar G’ having no e productions.

a) e ∈ L(G)

b) w ∉ L(G)

c) e ∉ L(G)

d) w ∈ L(G)

### View Answer

7. For each production in P of the form:

A-> x1x2x3…xn

put into P’ that production as well as all those generated by replacing null variables with e in all possible combinations. If all x(i) are nullable,

a) A->e is put into P’

b) A->e is not put into P’

c) e is a member of G’

d) None of the mentioned

### View Answer

8. For the given grammar G:

S->ABaC

A->BC

B->b| e

C->D| e

D-> d

Remove the e productions and generate the number of productions from S in the modified or simplified grammar.

a) 6

b) 7

c) 5

d) 8

### View Answer

9. Consider G=({S,A,B,E}, {a,b,c},P,S), where P consists of S →AB, A →a, B →b and E →c.

Number of productions in P’ after removal of useless symbols:

a) 4

b) 3

c) 2

d) 5

### View Answer

10. Given grammar G:

S->aS| AB

A-> e

B-> e

D-> b

Reduce the grammar, removing all the e productions:

a) S->aS| AB| A| B, D-> b

b) S->aS| AB| A| B| a, D-> b

c) S->aS| AB| A| B

d) None of the mentioned

### View Answer

## Set 4

1. Which among the following is the format of unit production?

a) A->B

b) A->b

c) B->Aa

d) None of the mentioned

### View Answer

2. Given Grammar G:

S->aA

A->a| A

B->B

The number of productions to be removed immediately as Unit productions:

a) 0

b) 1

c) 2

d) 3

### View Answer

3. Given grammar:

S->aA

A->a

A->B

B-> A

B->bb

Which of the following is the production of B after simplification by removal of unit productions?

a) A

b) bb

c) aA

d) A| bb

### View Answer

4. If grammar G is unambiguous, G’ produced after the removal of Unit production will be:

a) ambiguous

b) unambiguous

c) finite

d) cannot be said

### View Answer

5. If C is A-derivable, C->B is a production, and B ¹ A, then B is

a) nullable

b) Non-derivable

c) A-derivable

d) None of the mentioned

### View Answer

6. A can be A-> derivable if and only if __________

a) A-> A is actually a production

b) A->B, B-> A exists

c) Both (a) and (b)

d) None of the mentioned

### View Answer

7. Given Grammar:

T-> T+R| R

R-> R*V| V

V->(T)| u

When unit productions are deleted we are left with

T-> T+R| _______|(T)| u

R->R*V|(T)| u

V-> (T)| u

Fill in the blank:

a) T*V

b) T+V

c) R*T

d) R*V

### View Answer

8. Given grammar G:

S-> ABA, A->aA|e, B-> bB|e

Eliminate e and unit productions. State the number of productions the starting variable holds?

a) 6

b) 7

c) 9

d) 5

### View Answer

9. Given grammar G:

S-> A| B| C

A-> aAa| B

B-> bB|bb

C->aCaa|D

D->baD|abD|aa

Eliminate e and unit productions and state the number of variables left?

a) 5

b) 4

c) 3

d) 2

### View Answer

10. Which of the following variables in the given grammar is called live variable?

S->AB

A->a

a) S

b) A

c) B

d) None of the mentioned

### View Answer

## Set 5

1. Which of the following does not belong to input alphabet if S={a, b}* for any language?

a) a

b) b

c) e

d) none of the mentioned

### View Answer

2. The number of final states we need as per the given language?

Language L: {an| n is even or divisible by 3}

a) 1

b) 2

c) 3

d) 4

### View Answer

3. State true or false:

Statement: Both NFA and e-NFA recognize exactly the same languages.

a) true

b) false

### View Answer

4. Design a NFA for the language:

L: {an| n is even or divisible by 3}

Which of the following methods can be used to simulate the same.

a) e-NFA

b) Power Construction Method

c) Both (a) and (b)

d) None of the mentioned

### View Answer

5. Which of the following belongs to the epsilon closure set of a?

a) {f1, f2, f3}

b) {a, f1, f2, f3}

c) {f1, f2}

d) none of the mentioned

### View Answer

6. The number of elements present in the e-closure(f2) in the given diagram:

a) 0

b) 1

c) 2

d) 3

### View Answer

7. Which of the steps are non useful while eliminating the e-transitions for the given diagram?

a) Make a as accepting state of N’ if ECLOSE(p) contains an accepting state of N

b) Add an arc a to f1 labelled a if there is an arc labelled a in N from some state in ECLOSE(a) to f1

c) Delete all arcs labelled as e

d) None of the mentioned

### View Answer

8. Remove all the epsilon transitions in the given diagram and compute the number of a-transitions in the result?

a) 5

b) 7

c) 9

d) 6