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

View solution

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

View solution

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

View solution

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