If G is a grammer with productions S- SaS- aSb- bSa- SS-where S is the start variable- then which one of the following strings is not generated by G-

The given grammer is nbsp;S→ SaS| aSb| bSa| SS|ϵ nbsp; generates all strings with equal number of 'a' and 'b' nbsp; Now, S→ SaS can only generate string ...

You visited us 1 times! Enjoying our articles? Unlock Full Access!

Byju's Answer

Other

Objective Session 3

If G is a gra...

Question

If G is a grammer with productions

$S \to S a S ∣ a S b ∣ b S a ∣ S S ∣ ϵ$

where S is the start variable, then which one of the following strings is not generated by G?

Open in App

Solution

The given grammer is $S \to S a S ∣ a S b ∣ b S a ∣ S S ∣ ϵ$

generates all strings with equal number of 'a' and 'b'

Now, $S \to S a S$ can only generate strings where 'a' is more than 'b' since on left and right of 'a' in SaS, S will have only strings with $n_{a} = n_{b} o r n_{a} > n_{b}$ .

So, option (d) "babba" which is a string with $n_{b} > n_{a}$ is not possible to generate by the given grammer.

Suggest Corrections

Similar questions

Q. Consider the following CFG.

S \to a S b | b S a | a S | b S | a

Which of the following string cannot be generated by given CFG?

Q. Consider the CFG with {S, A, B} as the non-terminal alphabet, {a, b} as the terminal alphabet, S as the start symbol and the following set of production rules

$S \to b A$	$S \to a B$
$A \to a$	$B \to b$
$A \to a S$	$B \to b S$
$A \to b A A$	$B \to a B B$

Which of the following string is generated by the grammar?

Q. A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals.

S \to a S | A

A \to a A b | b A a | ε

Which of the following strings is generated by the grammar above?

Q. Consider the following grammer:
S

\to

aSB|d
B

\to

b

The number of reduction steps taken by a bottom-up parser while accepting the string aaadbbb is _____.

Q. Let G=({S},{a,b},R,S) be a context free grammar where the rule set R is

S \to a S b | S S | ϵ

Which of the following statements is true?

Join BYJU'S Learning Program

If G is a grammer with productions S→SaS∣aSb∣bSa∣SS∣ϵ where S is the start variable, then which one of the following strings is not generated by G?

If G is a grammer with productions

$S \to S a S ∣ a S b ∣ b S a ∣ S S ∣ ϵ$

where S is the start variable, then which one of the following strings is not generated by G?