adplus-dvertising
frame-decoration

Question

A context free grammar for L = { w | n0 (w) > n1 (w)} is given by :

a.

S → 0 | 0 S | 1 S S

b.

S → 0 S | 1 S | 0 S S | 1 S S | 0 | 1

c.

S → 0 | 0 S | 1 S S | S 1 S |S S 1

d.

S → 0 S | 1 S | 0 | 1

Answer: (c).S → 0 | 0 S | 1 S S | S 1 S |S S 1

Engage with the Community - Add Your Comment

Confused About the Answer? Ask for Details Here.

Know the Explanation? Add it Here.

Q. A context free grammar for L = { w | n0 (w) > n1 (w)} is given by :

Similar Questions

Discover Related MCQs

Q. Given the following two statements :

S1: If L1 and L2 are recursively enumerable languages over Σ, then L1 ⋃ L2 and L1 ⌒ L2 are also recursively enumerable.

S2: The set of recursively enumerable languages is countable.

Which of the following is correct?

Q. Given the following grammars :

G1: S → AB|aaB

A → aA | ∈

B → bB | ∈

G2: S → A | B

A → a A b | ab

B → a b B | ∈

Which of the following is correct?

Q. Let L be any language. Define even (W)  as the  strings  obtained by extracting from W the letters in the even-numbered positions and even (L) = {even (W) | W ԑ L}. We define another language Chop (L) by removing the two leftmost symbols of every string in L given by Chop(L) = {W | v W ԑ L,with | v | = 2}.

If L is regular language then

Q. Given the following two grammars :

G1 :     S → AB | aaB

A → a | Aa

B → b

G2: S→ aSbS|bSaS|λ

Which statement is correct ?

Q. Match the following:

List-I                                                            List-II

a. Chomsky Normal form                       i.  S→ bSS|aS|c

b. Greibach Normal form                        ii.  S→ aSb|ab

c. S-grammar                                           iii. S→ AS|a

                                                                         A→ SA|b

d. |LL grammar                                        iv. S→ aBSB

                                                                         B→ b

Codes:
a       b       c       d

Q. Given the following two languages :

L1 = {anbn |n≥1} ∪ {a}

L2= {w C wR|we {a,b}*}

Which statement is correct ?

Q. The solution of the recurrence relation of T(n) = 3T ( floor (n/4) ) +  n is

Q. The number of strings of length 4 that are generated by the regular expression (0|?) 1+2* (3|?), where | is an alternation character, {+, *} are quantification characters, and ? is the null string, is:

Q. Which of the following is FALSE ?

Q. Consider the languages L1 = ϕ, and L2 = {1}. Which one of the following represents
L1* U L2* L1* ?

Q. Given the following statements :
(A) A class of languages that is closed under union and complementation has to be closed under intersection.
(B) A class of languages that is closed under union and intersection has to be closed under complementation.
Which of the following options is correct?

Q. Given the following two languages:

L1 = {a^nb^n|n≥0, n≠100}
L2 = {w ϵ {a,b,c}*| na(w) = nb(w) = nc(w)}

Which of the following options is correct?

Q. Given the following two statements:

A. L = {w|na(w) = nb(w)} is deterministic context free language, but not linear.
B. L = {an bn} U {an b2n} is linear, but not deterministic context free language.

Which of the following options is correct?

Q. Which of the following pairs have different expressive power?

Q. Which of the following statements is false?

Q. Let C be a binary linear code with minimum distance 2t + 1 then it can correct upto ............bits of error.

Q. From the given data below:

a b b a a b b a a b

which one of the following is not a word in the dictionary created by LZ-coding (the initial words are a, b)?

Q. The number of strings of length 4 that are generated by the regular expression (0+1+|2+3+)*, where | is an alternation character and {+, *} are quantification characters, is:

Q. Which of the following is FALSE ?

Q. The regular grammar for the language L = {a^nb^m | n + m is even} is given by

(A) S → S1 | S2
S1 → a S1 | A1
A1 → b A1 | λ
S2 → aaS2 | A2
A2 → b A2 | λ
(B) S → S1 | S2
S1 → a S1 | a A1
S2 → aa S2 | A2
A1 → bA1 | λ
A2 → bA2 | λ
(C) S → S1 | S2
S1 → aaa S1 | aA1
S2 → aaS2 | A2
A1 → bA1 | λ
A2 → bA2 | λ
(D) S → S1 | S2
S1 → aa S1 | A1
S2 → aaS2 | aA2
A1 → bbA1 | λ
A2 → bbA2 | b