adplus-dvertising
frame-decoration

Question

Let G = (V, T, S, P) be a context-free grammar such that every one of its productions is of the form A → n, with |v| = k > 1. The derivation tree for any string W ϵ L (G) has a height such that

a.

A

b.

B

c.

C

d.

D

Answer: (d).D

Engage with the Community - Add Your Comment

Confused About the Answer? Ask for Details Here.

Know the Explanation? Add it Here.

Q. Let G = (V, T, S, P) be a context-free grammar such that every one of its productions is of the form A → n, with |v| = k > 1. The derivation tree for any string W ϵ L (G) has a...

Similar Questions

Discover Related MCQs

Q. Consider the following linear programming problem:

Max. z = 0.50x2 – 0.10x1
Subject to the constraints
2x1 + 5x2 ≤ 80
x1 + x2 ≤ 20
and x1, x2 ≥ 0

The total maximum profit (z) for the above problem is:

Q. The regular expression for the complement of the language L = {anbm|n≥4, m≤3} is:

Q. Consider the following two languages:

L1 = {0i1j | gcd(i,j)=1}
L2 is any subset of 0*.

Which of the following is correct?

Q. Let L be the language generated by regular expression 0*10* and accepted by the deterministic finite automata M. Consider the relation RM defined by M. As all states are reachable from the start state, RM has ................ equivalence classes.

Q. Let L = {0^n1^n | n≥0} be a context free language.
Which of the following is correct?

Q. Given a Turing Machine

M = ({q0,q1,q2,q3}, {a,b}, {a,b,B}, δ, B, {q3})

Where δ is a transition function defined as

δ(q0,a) = (q1,a,R)
δ(q1,b) = (q2,b,R)
δ(q2,a) = (q2,a,R)
δ(q2,b) = (q3,b,R)

The language L(M) accepted by the Turing Machine is given as:

Q. Match the following :

List - I                                                             List - II
(a) {a^n b^n|n > 0} is a deterministic                  (i) but not recursive language
context free language        
(b) The complement of {a^n b^n a^n|n > 0}         (ii) but not context free language
is a context free language
(c) {a^n b^n a^n} is context sensitive language (iii) but can not be accepted by a deterministic pushdown automation
(d) L is a recursive language                         (iv) but not regular

Codes :
     (a)   (b)   (c)   (d)

Q. The language of all non-null strings of a’s can be defined by a context free grammar as
follow :

S→a S|S a| a

The word a^3 can be generated by ................ different trees.

Q. The context free grammar given by

S→XYX
X→aX|bX|λ
Y→bbb

generates the language which is defined by regular expression:

Q. There are exactly ................ different finite automata with three states x, y and z over the alphabet {a, b} where x is always the start state.

Q. Given the following two languages :

L1={a^n b a^n|n>0}
L2={a^n b a^n b^n+1|n>0}

Which of the following is correct?

Q. Consider a language A defined over the alphabet ∑={0, 1} as A = {0^[n/2] 1^n: n >= 0} .
The expression [n/2] means the floor of n/2, or what you get by rounding n/2 down to the nearest integer.

Which of the following is not an example of a string in A ?

Q. A grammar G is LL(1) if and only if the following conditions hold for two distinct productions A → α | β

I. First (α) ∩ First (β) ≠ {a} where a is some terminal symbol of the grammar.
II. First (α) ∩ First (β) ≠ λ
III. First (α) ∩ Follow(A) = φ if λ є First (β)

Q. A shift reduce parser suffers from

Q. The context free grammar for language L = {a^nb^mc^k | k = |n - m|, n≥0,m≥0,k≥0} is

Q. The number of states in a minimal deterministic finite automaton corresponding to the language L = { an | n≥4 } is

Q. Regular expression for the language L = { w ∈ {0, 1}* | w has no pair of consecutive zeros} is

Q. Consider the following two languages:

L1 = {a^n b^l a^k | n + l +k>5 }
L2 = {a^n b^l a^k |n>5, l >3, k≤ l }

Which of the following is true?

Q. LL grammar for the language L = {a^n b^m c^n+m | m≥0, n≥0} is

Q. Assume the statements S1 and S2 given as:

S1: Given a context free grammar G, 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?