Read the following and answer the questions that follow. A machine is represented by states Q, input alphabet Σ, transition function δ. Initial state q0 and final state F. The machine accepts all the strings over Σ = {a, b}, which start and ended with any combination of all alphabet and abb works /lies as substring in all the strings to be accepted.
For the above specified passage, which of the following represent the grammar for the language accepted the machine?
S→AabbA, A→aA|bA|ε
The language is \((a+b)^{*}abb(a+b)^{*}\). A grammar for it needs one nonterminal that generates \((a+b)^{*}\) (any string of a and b, including the empty string), placed on both sides of the terminal word abb.
Step 1 — A → aA | bA | ε generates every string over {a, b}: each step appends a or b, and ε stops the derivation.
Step 2 — S → AabbA then yields (any string) abb (any string), which is exactly the required language. For example S ⇒ AabbA ⇒ babbA ⇒ babba.
The grammar S → AabbB with A → aA | ε and B → bB | ε gives only amabbbn, so it cannot derive babb. The grammar S → abbA forces every string to start with abb and cannot derive aabb. The grammar S → Aabb forces every string to end with abb and cannot derive abba.
S→AabbA, A→aA|bA|ε option is correct.
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 :
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
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.
