Theory of Automata
Context-Free Grammars
Q.

A CFG(Context Free Grammar) is said to be in Chomsky Normal Form (CNF), if all the productions are of the form A -> BC or A -> a. Let G be a CFG in CNF. To derive a string of terminals of length x, the number of products to be used is
A.  

2x - 1

 B.  

2x

 C.  

2x + 1

 D.  

2x
Similar Questions
1.

Which of the following pairs have DIFFERENT expressive power?
A.  

Deterministic finite automata(DFA) and Non-deterministic finite automata(NFA)

 B.  

Deterministic push down automata(DPDA)and Non-deterministic push down automata(NPDA)

 C.  

Deterministic single-tape Turing machine and Non-deterministic single-tape Turing machine

 D.  

Single-tape Turing machine and multi-tape Turing machine
2.

Assume Statement S1 and S2 defined as:S1:L2-L1 is recursive enumerable Where L1 and L2 are recursive and recursive enumerable respectively. S2: The set of all Turnig machine is countable. Which of the following is true?
A.  

S1 is correct ans S2 is not correct

 B.  

Both S1 and S2 are correct

 C.  

Both S1 and S2 are not correct

 D.  

S1 is not correct and S2 is correct
3.

A context free language is called ambigous if ______________
A.  

it has 2 or more left derivations for some terminal string w e L(G)

 B.  

it has 2 more or more right derivations for some terminal string w e L(G)

 C.  

it has two or more left & right derivations for some terminal string w e L(G)

 D.  

None of the mentioned
4.

Which of the following  statement is false ?
A.  

The CFG can be converted to Chomsky normal form

 B.  

The CFG can be converted to Greibach normal form

 C.  

CFG is accepted by pushdown automata

 D.  

None of the mentioned
5.

The context free grammer S->SS | oS1 | 1So |  e generates
A.  

Equal number of O's and 1's

 B.  

Unequal number of O's and 1's

 C.  

Number of O's followd by any number of 1's

 D.  

None of the mentioned
6.

Which of the following  statement is false ?
A.  

In derivation tree, the label of each leaf node is terminal

 B.  

In derivation tree, the label of all nodes except leaf nodes is a variables

 C.  

In derivation tree, if the root of a sub tree is X then it is called --tree

 D.  

None of the mentioned
7.

Push down automata excepts which language ?
A.  

Context Sensitive Language

 B.  

Context free Language

 C.  

Recursive Language

 D.  

None of the mentioned
8.

A regular Grammer is a ___________
A.  

CFG

 B.  

Non CFG

 C.  

English Grammer

 D.  

None of the mentioned
9.

A CFG is close under ________
A.  

Union

 B.  

Kleene star

 C.  

Concatenation

 D.  

None of the mentioned
10.

Which of these does not belong to CFG ?
A.  

Terminal Symbol

 B.  

Non Terminal Symbol

 C.  

Start  Symbol

 D.  

End Symbol
THEORY OF AUTOMATA TOPICS