Properties of Context-Free Computing Languages

This quiz contains MCQs on CFL closure properties and other standard forms, Chomsky normal form, regular languages, eliminating useless symbols, epsilon and unit productions.

Start Quiz

Which of the following does not have left recursions?

Chomsky normal form

Greibach normal form

Backus-Naur Form

All of the above

Every grammar in Chomsky's normal form is

Regular

Context-sensitive

Context-free

All of the above

Which of the following production rules is/are accepted by Chomsky grammar?

A->BC

A->a

S->e

All of the above

Which of the following grammars are in Chomsky's normal form?

S->AB|BC|CD, A->0, B->1, C->2, D->3

S->AB, S->BCA|0|1|2|3

S->ABa, A->aab, B->Ac

All of the above

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

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

Restricted form

Parsed form

Normal form

All of the above

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

Yes

Which of the following is called Bar-Hillel lemma?

Pumping lemma for regular language

Pumping lemma for context free languages

Pumping lemma for context sensitive languages

None of the above

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 is

2p+1

Which of the following positively affects the pumping lemma’s restrictions and requirements?

{aibici|i>=0}

{0i1i|i>=0}

{ss|s∈{a,b}*}

None of the above

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

{aibici|i>=0}

{ss|s∈{a,b}*}

The set legal C programs

None of the above

It is not possible to use Ogden’s lemma when pumping lemma fails. True or false?