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 - aS - A A - aAb - bAa - -Which of the following strings is generated by the grammar above-

Given grammar will generate string aabbaab nbsp; Whose derivation is given below: S → aS S → aA S → aaAb S → aabAab S → aabbAaab S → aabbaab nbsp; ...

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

Byju's Answer

Other

Construction of CFG Part - 1

A CFG G is gi...

Question

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?

Open in App

Solution

Given grammar will generate string aabbaab
Whose derivation is given below:
$S \to a S$
$S \to a A$
$S \to a a A b$
$S \to a a b A a b$
$S \to a a b b A a a b$
$S \to a a b b a a b$

Suggest Corrections

Similar questions

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 | ε

For the correct answer in above Question, how many steps are required to derive the string and how many parse trees are there?

Q. Consider a CFG with the following productions.

S \to A A | B

A \to 0 A | A 0 | 1

B \to 0 B 00 | 1

S is the start symbol, A and B are non-terminals and 0 and 1 are the terminals. The language generated by this grammar is

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. In the context-free grammar below, S is the start symbol, a and b are terminals, and

ε

denotes the empty string

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

Which of the following strings is NOT generated by grammar?

Q. A context-free grammar has a set of terminals {0. 1, -}, a set of non-terminals {N, p}, where N is the strats symbol and production s given by the following :

N \to 0 | P | - P

P \to | P 0 | P 1

What can be said about the language generated by this grammar ?

Join BYJU'S Learning Program

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→ aS | A A→ aAb | bAa | ε Which of the following strings is generated by the grammar above?

Given grammar will generate string aabbaab Whose derivation is given below: S→ aS S→ aA S→ aaAb S→ aabAab S→ aabbAaab S→ aabbaab

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?

Given grammar will generate string aabbaab
Whose derivation is given below:
$S \to a S$
$S \to a A$
$S \to a a A b$
$S \to a a b A a b$
$S \to a a b b A a a b$
$S \to a a b b a a b$