Consider the following CFG-S- aSb -bSa- aS - bS- aWhich of the following string cannot be generated by given CFG-

(A)aaabb : S⇒ aSb⇒ aaSbb nbsp; ⇒ aaabb (B)aaba: S⇒ aS ⇒ aaS nbsp;⇒ aabS nbsp;⇒ aaba nbsp; nbsp; (C)aaaab: S⇒ aSb ⇒ aaSb ⇒ aaaSb⇒ aaaab (D) aabbb ca ...

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

Byju's Answer

Standard IV

Mathematics

Encoding and Decoding Patterns

Consider the ...

Question

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?

aaba

No worries! We‘ve got your back. Try BYJU‘S free classes today!

aabbb

Right on! Give the BNAT exam to get a 100% scholarship for BYJUS courses

aaaab

No worries! We‘ve got your back. Try BYJU‘S free classes today!

aaabb

No worries! We‘ve got your back. Try BYJU‘S free classes today!

Open in App

Solution

The correct option is B aabbb
$(A) a a a b b : S \Rightarrow a S b \Rightarrow a a S b b \Rightarrow a a a b b$

$(B) a a b a : S \Rightarrow a S \Rightarrow a a S \Rightarrow a a b S \Rightarrow a a b a$

$(C) a a a a b : S \Rightarrow a S b \Rightarrow a a S b \Rightarrow a a a S b \Rightarrow a a a a b$

$(D) aabbb cannot be drived using given grammar$

Suggest Corrections

Similar questions

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. Consider the following grammar:

S \to a S B | d

B \to b

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

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. A program attempts to generate as many permutations as possible of the string, 'abcd' by pushing the characters a, b, c, d in the same order onto a stack, but it may pop off the loop character at anytime. Which one of the following strings CANNOT be generated using this program?

Q. A program attempts to generate as many permutations as possible of the string 'xyzw' by pushnig the characters x, y, z, w in the same order onto a stack, but it may pop off the top charaacter at any time. Which on of the following strings CANNOT be generated using this program?

Join BYJU'S Learning Program

Consider the following CFG. S→aSb |bSa| aS |bS|a Which of the following string cannot be generated by given CFG?

The correct option is B aabbb(A)aaabb:S⇒aSb⇒aaSbb⇒aaabb (B)aaba:S⇒aS⇒aaS⇒aabS⇒aaba (C)aaaab:S⇒aSb⇒aaSb⇒aaaSb⇒aaaab (D) aabbb cannot be drived using given grammar

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?