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

Q. Let G be a grammar. When the production in G satisfy certain restrictions, then G is said to be in ___________.

View solution

Q. Let G be a grammar: S->AB|e, A->a, B->b
Is the given grammar in CNF?

View solution

Q. Which of the following is called Bar-Hillel lemma?

View solution

Q. Which of the expressions correctly is an requirement of the pumping lemma for the context free languages?

View solution

Q. Let L be a CFL. Then there is an integer n so that for any u that belong to language L satisfying
|t|>=n, there are strings u, v, w, x, y and z satisfying

t=uvwxy.

Let p be the number of variables in CNF form of the context free grammar. The value of n in terms of p :

View solution

Q. Which of the following gives a positive result to the pumping lemma restrictions and requirements?

View solution

Q. Using pumping lemma, which of the following cannot be proved as ‘not a CFL’?

View solution

Q. State true or false:
Statement: We cannot use Ogden’s lemma when pumping lemma fails.

View solution