I got the answer, It\'s S -> epsilon, S -> [S], S -> {S}, and S ->(S) Consider a

Question

I got the answer, It's S -> epsilon, S -> [S], S -> {S}, and S ->(S)

Consider a set of opening brackets (L (and their corresponding closing brackets )L, respectively. A string is well nested if each opening brace is matched to a corresponding closing brace and no two matched pairs cross each other. Eg., the string"H)())( is well nested, whereas "( is not. Similarly, "T)" is not well nested either. Select all the rules for a context-free grammar that generates well nested strings of these brackets. Select one or more: S [S]

Explanation / Answer

S -> | [S] | {S} | (S) ===> Not exactly correct it fails for . (()) [ ] such example

Lets take some example of balanced ones


(( [[ ]] ) )


S ->(S)
S ->( ( S ) )
S ->( ( [ S ] ) )
S ->( ( [ [ S ] ] ) )
S ->( ( [ [ ] ] ) ) Balanced

The above grammar cannot generate Strings like
(( )) [ ]

Above is Impoissible

=================================================================
Correct CFG : ANSWER
S -> , S -> [S], S -> {S}, S ->(S) AND S - > SS


The above grammar WILL BE ABLE TO generate Strings like
(( )) [ ]

S - > SS

- > (S)S
-> ((S))[S]
->(())[S]
->(())[]

Thanks

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.