Q. 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:

View solution

Q. Given grammar G:
S->aS| AB

A-> e

B-> e

D-> b

Reduce the grammar, removing all the e productions:

View solution

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

View solution

Q. Given Grammar G:
S->aA

A->a| A

B->B

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

View solution

Q. 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?

View solution

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

View solution

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

View solution

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

View solution

Q. 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:

View solution

Q. 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?

View solution

Q. 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?

View solution

Q. Which of the following variables in the given grammar is called live variable?
S->AB

A->a

View solution

Q. The format: A->aB refers to which of the following?

View solution

Q. Which of the following does not have left recursions?

View solution

Q. Every grammar in Chomsky Normal Form is:

View solution

Q. Which of the production rule can be accepted by Chomsky grammar?

View solution

Q. Given grammar G:
(1)S->AS

(2)S->AAS

(3)A->SA

(4)A->aa

Which of the following productions denies the format of Chomsky Normal Form?

View solution

Q. Which of the following grammars are in Chomsky Normal Form:

View solution

Q. With reference to the process of conversion of a context free grammar to CNF, the number of variables to be introduced for the terminals are:
S->ABa

A->aab

B->Ac

View solution

Q. In which of the following, does the CNF conversion find its use?

View solution