MyQuestionIcon

1

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

Context-Free Grammars

In the contex...

Question

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?

Open in App

Solution

L(G)= Set of all palindrome strings.
"baba" is not a palindrome string

Suggest Corrections

thumbs-up

0

Similar questions

Q. In the context-free grammar below, S is the start symbol, a and b are terminals, and

ϵ

denotes the empty strings

S \to

ϵ

A \to

ϵ

The grammar generates the language

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. Which of the following statements are true?
1. Every left-recursive grammar can be converted to a right-recursive grammar and vice-versa.
2. All

ε

-productions can be removed from any context-free grammar by suitable transformations.
3. The language generated by a context-free grammar all of whose productions are of the form X

\to w

\to w Y

(where, w is a string of terminals and Y is a non-terminal), is always regular.
4. The derivations trees of strings generated by a context-free grammar in Chomsky Normal Form are always binary trees.

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

The language generated by the above grammar over the alphabet {a,b} is the set of

Q. Consider the following context-free grammar over the alphabet

\sum = {a, b, c}

with S as the start symbol:

S \to a b S c T | a b c T

T \to b T | b

Which one of the following represents the language generated by the above grammar?

View More

Join BYJU'S Learning Program

similar_icon

Related Videos

lock

Context-Free Grammars

OTHER

Watch in App

explore_more_icon

Explore more

Context-Free Grammars

Join BYJU'S Learning Program

CrossIcon