Q. CFGs can be parsed in polynomial time using__________

View solution

Q. Suppose A->xBz and B->y, then the simplified grammar would be:

View solution

Q. Given Grammar: S->A, A->aA, A->e, B->bA
Which among the following productions are Useless productions?

View solution

Q. Given:
S->…->xAy->…->w

if ____________, then A is useful, else useless symbol.

View solution

Q. Given:
S->aSb

S->e

S-> A

A->aA

B->C

C->D

The ratio of number of useless variables to number of useless production is:

View solution

Q. Given grammar G:
S->aS|A|C

A->a

B->aa

C->aCb

Find the set of variables thet can produce strings only with the set of terminals.

View solution

Q. Given grammar:
S->aS|A

A->a

B->aa

Find the number of variables reachable from the Starting Variable?

View solution

Q. Inorder to simplify a context free grammar, we can skip the following operation:

View solution

Q. Given a Grammar G:
S->aA

A->a

A->B

B->A

B->bb

Which among the following will be the simplified grammar?

View solution

Q. Simplify the given grammar:
A-> a| aaA| abBc

B-> abba| b

View solution

Q. In context to the process of removing useless symbols, which of the following is correct?

View solution

Q. The use of variable dependency graph is in:

View solution

Q. The variable which produces an epsilon is called:

View solution

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

View solution

Q. Simplify the given grammar:
S->aXb

X->aXb | e

View solution

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

View solution

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