Bissoy.com
Doctors Medicines MCQs Q&A

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

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 Correct Answer 2p+1

This inequation has been derived from derivation tree for t which must have height at least p+2(It has more than 2p leaf nodes, and therefore its height is >p+1).

Related Questions

Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine M. Which of the following decision problems are undecidable? I. Given a regular expression R and a string w, is w ∈ L(R)? II. Given a context-free grammar G, is L(G) = ϕ? III. Given a context-free grammar G, is L(G) = ∑* for some alphabet ∑? IV. Given a Turing machine M and a string w, is w ∈ L(M)?  
Let L1, L2 be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT? I. L1 ∪ L2 is context-free II. L̅1 is context-free III. L1 – R is context-free IV. L1 ∩ L2 is context-free
What is the difference between a CFL and an LED lamp? 1. To produce light, a CFL uses mercury vapour and phosphor while an LED lamp uses semiconductor material. 2. The average life span of a CFL is much longer than that of an LED lamp. 3. A CFL is less energy-efficient as compared to an LED lamp. Which of the statements given above is/are correct?
What is the difference between a CFL and an LED lamp? 1. To produce light, a CFL uses mercury vapour and phosphor while an LED lamp uses semi-conductor material. 2. The average life span of a CFL is much longer than that of an LED lamp. 3. A CFL is less energy-efficient as compared to an LED lamp. Which of the statements given above is/are correct?
What is the difference between a CFL and an LED Lamp?
1. To produce light, a CFL uses mercury vapour and phosphor while an LED lamp uses semi-conductor material.
2. The average life span of a CFL is much longer than of an LED lamp.
3. A CFL is less energy efficient as compared to an LED lamp.
Which of the statements given above is/are correct?
Which of the following statements are true of the teaching of grammar. A. Teaching of rules at the initial stage does not lend much to language learning. B. Rules of grammar are essential during the formative years of language learning. C. Grammar teaching should move from meaning to form. D. Grammar teaching should move from form to meaning. 
Consider the following grammar G: P → Q + R | Q – R | Q | R Q → q | r R → r | s where P, Q, and R are non-terminal symbols, and q, r, and s are terminal symbols. Which of the following statement(s) is/are correct? S1. LL(1) can parse all strings that are generated using grammar G S2. LR(1) can parse all strings that are generated using grammar G
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
Which of the following statement(s) is/are FALSE? (i) Language L1 = {anbmcndm, n ≥ 0, m ≥ 0} is not context free grammar. (ii) Language L2 = {anbncn, n ≥ 0} is a context free grammar.
Let G be a grammar: S->AB|e, A->a, B->b Is the given grammar in CNF?