1. Which of the following is not a notion of Context free grammars?

a) Recursive Inference

b) Derivations

c) Sentential forms

d) All of the mentioned

### View Answer

Answer: d

Explanation: The following are the notions to express Context free grammars:

a) Recursive Inferences

b) Derivations

c) Sentential form

d) Parse trees

Explanation: The following are the notions to express Context free grammars:

a) Recursive Inferences

b) Derivations

c) Sentential form

d) Parse trees

Statement: The recursive inference procedure determines that string w is in the language of the variable A, A being the starting variable.

a) true

b) false

### View Answer

Answer: a

Explanation: We apply the productions of CFG to infer that certain strings are in the language of a certain variable.

Explanation: We apply the productions of CFG to infer that certain strings are in the language of a certain variable.

a) L1*

b) L2UL1

c) L1.L2

d) All of the mentioned

### View Answer

Answer: d

Explanation: The following is a theorem which states the closure property of context free languages which includes Kleene operation, Union operation and Dot operation.

Explanation: The following is a theorem which states the closure property of context free languages which includes Kleene operation, Union operation and Dot operation.

(011+1)*(01)*

a) 4

b) 3

c) 5

d) 6

### View Answer

Answer: c

Explanation: The grammar can be written as:

S->BC

B->AB|ε

A->011|1

C->DC|ε

D->01

Explanation: The grammar can be written as:

S->BC

B->AB|ε

A->011|1

C->DC|ε

D->01

Statement: A CNF parse tree’s string yield (w) can no longer be 2h-1.

a) true

b) false

### View Answer

Answer: a

Explanation: It is the parse tree theorem which states:

Given: Suppose we have a parse tree for a string w, according to a CNF grammar, G=(V, T, P, S). Let h be the height of the parse tree. Now, Implication: |w|<=2h-1.

Explanation: It is the parse tree theorem which states:

Given: Suppose we have a parse tree for a string w, according to a CNF grammar, G=(V, T, P, S). Let h be the height of the parse tree. Now, Implication: |w|<=2h-1.

a) YACC

b) GNU Bison

c) YACC and GNU Bison

d) None of the mentioned

### View Answer

Answer: c

Explanation: YACC is a computer code for UNIX operating system which generates a LALR parser. On the other hand GNU Bison or Bison can generate LALR and GLR parsers.

Explanation: YACC is a computer code for UNIX operating system which generates a LALR parser. On the other hand GNU Bison or Bison can generate LALR and GLR parsers.

a) LL parser

b) Recursive descent parser

c) Earley parsers

d) All of the mentioned

### View Answer

Answer: d

Explanation: All the following mentioned are top down parsers and begin their operation from the starting symbol.

Explanation: All the following mentioned are top down parsers and begin their operation from the starting symbol.

a) Recursive Descent parser

b) no backtracking

c) Recursive Descent parser and no backtracking

d) None of the mentioned

### View Answer

Answer: c

Explanation: Predictive parsing is possible only for the class of LL-grammars, which are the CFG for which there exists some positive integer k that allows a recursive descent parser to decide which production to use by examining only the next k tokens of input.

Explanation: Predictive parsing is possible only for the class of LL-grammars, which are the CFG for which there exists some positive integer k that allows a recursive descent parser to decide which production to use by examining only the next k tokens of input.

Statement: There exists two inference approaches:

a) Recursive Inference

b) Derivation

a) true

b) partially true

c) false

d) none of the mentioned

### View Answer

Answer: a

Explanation: We apply the productions of a CFG to infer that certain strings are in a language of certain variable.

Explanation: We apply the productions of a CFG to infer that certain strings are in a language of certain variable.

Statement 1: Recursive Inference, using productions from head to body.

Statement 2: Derivations, using productions from body to head.

a) Statement 1 is true and Statement 2 is true

b) Statement 1 and Statement 2, both are false

c) Statement 1 is true and Statement 2 is false

d) Statement 2 is true and Statement 1 is true

### View Answer

Answer: b

Explanation: Both the statements are false. Recursive Inference, using productions from body to head. Derivations, using productions from head to body.

Explanation: Both the statements are false. Recursive Inference, using productions from body to head. Derivations, using productions from head to body.

a) Every CFG for L is ambiguous

b) Every CFG for L is unambiguous

c) Every CFG is also regular

d) None of the mentioned

### View Answer

Answer: a

Explanation: A CFL L is said to be inherently ambiguous if every CFG for L is ambiguous.

Explanation: A CFL L is said to be inherently ambiguous if every CFG for L is ambiguous.

a) 3 * 28

b) 2(3*8)

c) 2(3+8)

d) None of the mentioned

### View Answer

Answer:b

Explanation: 2(m*n) states requires .

Explanation: 2(m*n) states requires .

a) True

b) False

c) May be true

d) None of the mentioned

### View Answer

Answer:a

Explanation: Use them as a flip flop output .

Explanation: Use them as a flip flop output .