1.Write a grammar that generates strings that contain matched brackets and paren

Question

1.Write a grammar that generates strings that contain matched brackets and parentheses. Examples of valid strings are:

Examples of invalid strings are:

2. Given the following grammar:

<sentence> -> <left> a <right> b
<left> -> <left> b | b
<right> -> a <right> | a

Indicate which of the following strings are valid according to this grammar. For those that are valid, construct the parse tree.

baab

bbbaaaaab

bbbab

aabab

bbbaaabb

In English, describe the strings generated by this grammar as specifically as possible.

Explanation / Answer

1.

<start> -> <start> <start> | [ <start> ] | { <start> } | ( <start> ) | NULL

2.

Valid:
baab, bbbaaaaab,

Invalid:
bbbab, aabab, bbbaaabb

The grammar generates strings which begin with a sequence of 1 or more 'b', followed by a sequence of 2 or more 'a', further followed by a 'b'

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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