A context free grammar for \(L = \{ w \mid n_{0}(w) \gt n_{1}(w) \}\) is given by :
\(S \rightarrow 0 \mid 0S \mid 1SS \mid S1S \mid SS1\)
Every string generated from S must have strictly more 0s than 1s, and every such string must be derivable.
Each rule keeps the surplus positive: \(S \rightarrow 0\) has surplus 1, \(0S\) adds one more 0, and \(1SS\), \(S1S\), \(SS1\) add one 1 against two strings that each have surplus at least 1.
Placing the 1 before, between or after the two S parts lets the extra 1s appear anywhere, e.g. 001 via \(S \rightarrow SS1 \Rightarrow 001\) and 010 via \(S \rightarrow S1S\).
The grammar with only 0, 0S and 1SS cannot produce strings ending in 1 such as 001, while the other two produce strings like 1 that have more 1s.
Hence, \(S \rightarrow 0 \mid 0S \mid 1SS \mid S1S \mid SS1\).
Similar Questions
The following Context-Free Grammar (CFG) :
S → aB | bA
A → a | as | bAA
B → b | bs | aBB
will generate
The context free grammar given by
\(S \to XYX\)
\(X \to aX \mid bX \mid \lambda\)
\(Y \to bbb\)
generates the language which is defined by regular expression :
If all the production rules have single non - terminal symbol on the left side, the grammar defined is :
Match the following :
List - I List - II a. Chomsky Normal form i. \(S \to b\,S\,S \mid a\,S \mid c\) b. Greibach Normal form ii. \(S \to a\,S\,b \mid ab\) c. S-grammar iii. \(S \to AS \mid a\)
\(A \to SA \mid b\)d. LL grammar iv. \(S \to a\,B\,S\,B\)
\(B \to b\)The context free grammar for the language \(L = \{a^{n}b^{m}c^{k} \mid k = |n - m|, n \geq 0, m \geq 0, k \geq 0\}\) is
For the above specified passage, which of the following represent the grammar for the language accepted the machine?
Which of the folowing CFG(s) is/are in chomsky Normal form (All capital letters are variables & lower case are terminals)
A. S → ABC / AB
A → a
B → b
C → dB. X → RT / TR
T → t
R → XT / rC. P → qP / sQ
Q → r / sD. M → MN / MP
N → nm / n
P → pChoose the correct answer from the options given below:
Let G = (V, T, S, P) be a context-free grammar such that every one of its productions is of the form A → v, with |v| = K > 1. The derivation tree for any W ∈ L(G) has a height h such that
Important Questions from Context Free Grammars
- Which of the following Grammars is/are only Context Free?
A S $\rightarrow$ Ab
aS$\rightarrow$ aA
A$\rightarrow$ aB S $\rightarrow$ Ab
A $\rightarrow$ Sa
A $\rightarrow$ aC S $\rightarrow$ AS
S $\rightarrow$ aA
A$\rightarrow$ aD S $\rightarrow$ Ab
S $\rightarrow$ aA
A$\rightarrow$ aE S $\rightarrow$ Sb
A $\rightarrow$ Aa
A $\rightarrow$ $\varepsilon$
Choose the correct answer from the options given below: Which of the following grammars is (are)ambiguous ?
(1) S → SS | aSb | bSa |e(2) S → aSbS | bSaS |e
(3) S → aAB
A → bBb
B → A Ι eConsider the grammar,
G = S → abScB | e,
B→ bB | b.
What is the language generated by the given grammar ?
Consider the given grammar
S → Abc | adA → eS | Cr| ξ
C → f/p/ξ
Compute FIRST (A)Select the sentence which is meaningful and grammatically correct.
