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 :
\((a+b)^{*}(bbb)(a+b)^{*}\)
X generates any string over {a, b} including the empty string, which is \((a+b)^{*}\).
Y generates exactly bbb, and S concatenates X, Y and X.
So the language is \((a+b)^{*}\,bbb\,(a+b)^{*}\): all strings containing bbb as a substring.
The other expressions force bbb at the end, force a leading 'a', or allow exactly one symbol before bbb.
Hence, \((a+b)^{*}(bbb)(a+b)^{*}\).
Similar Questions
The following Context-Free Grammar (CFG) :
S → aB | bA
A → a | as | bAA
B → b | bs | aBB
will generate
A context free grammar for \(L = \{ w \mid n_{0}(w) \gt n_{1}(w) \}\) is given by :
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.
