Menu

Question Discussion & Solution

MCQ
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

forum Community Discussion

speaker_notes_off

No discussions yet. Be the first to start!

You must be logged in to participate in the discussion.

login Login to Discuss

auto_awesome Similar Questions

MCQ
1.
Which of the following language(s) generates more than one parse tree for a string ?

L1 = {a^nb^mc^md^n ? {a, b, c, d}* | n, m ? 0} 
      ? {a^nb^nc^md^m ? {a, b, c, d}* | n, m ? 0} 

L2 = {a^nb^mc^m ? {a, b, c}* | n, m ? 0} 
      ? {a^nb^nc^m ? {a, b, c}* | n, m ? 0}

L3 = {a^nb^mc^p ? {a, b, c}* | n ? m; n, m ? 0} 
      ? {a^nb^mc^p ? {a, b, c}* | m ? p; n, m ? 0}
forum Discussion
MCQ
2.
A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals.
S?aS?A
A?aAb?bAa??
Which of the following strings is generated by the grammar above?
forum Discussion
MCQ
3.
If P & R are regular and also given that if PQ=R, then?
forum Discussion
MCQ
4.
Consider the following grammars G1 and G2 respectively. Grammar - G1:

A1 ? A2A3
A2 ? A3A1 | b
A3 ? A1A1 | a
Grammar - G2:

S ? AA | 0
A ? SS | 1
Consider the following statements regarding above grammars: (I): This grammar is not left recursive and equivalent to grammar - G1:

A1 ? A2A3
A2 ?  A3A1 | b
A3 ? a | bA3A1 | aK | bA3A1K 
k ? A1A3A1 | A1A3A1K
(II): This grammar is not left recursive and equivalent to grammar - G2:

S ? A A | 0
A ? 0S | 1 | 0SK | 1K
K ? AS | ASK
forum Discussion
MCQ
5.
Assume the statements S1 and S2 given as:S1: Given a context free grammar, there exists an algorithm for determining whether L (G) is infinite.
S2: There exists an algorithm to determine whether two context free grammars generate the same language.
Which of the following is true?
forum Discussion

category More Theory of Automata Topics

article

Reqular Expressions

format_list_bulleted 114 MCQs
Practice arrow_forward
article

Finite Automata

format_list_bulleted 44 MCQs
Practice arrow_forward
article

Context Free Grammars

format_list_bulleted 76 MCQs
Practice arrow_forward
article

Push Down Automata

format_list_bulleted 37 MCQs
Practice arrow_forward
article

Regular and context free languages

format_list_bulleted 65 MCQs
Practice arrow_forward
article

Pumping Lemma

format_list_bulleted 14 MCQs
Practice arrow_forward
article

Turning Machine

format_list_bulleted 14 MCQs
Practice arrow_forward