Given the following grammar: <sentence> -> <sentence> <term>| <term> <term> -> <

Question

Given the following grammar:

<sentence> -> <sentence> <term>| <term>
<term> -> <begin> <end>
<begin> -> <begin> <left> | <left>
<end> -> <right> <end> | <right>
<left> -> a| b | c
<right> -> 1 | 2 | 3

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

a1b2c3
abc123
12ab
11aa22
ab12c3

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

Explanation / Answer

Each sentence is one or more letters followed by one or more numbers. #1: sentence -> sentence term -> sentence sentence term -> term term term -> begin end begin end begin end -> left right left right left right -> a 1 b 2 c 3 #2: sentence -> term -> begin end -> begin left right end -> begin left left right right end -> left left left right right right -> a b c 1 2 3 #3: INVALID #4: INVALID #5: sentence -> sentence term -> term term -> begin end begin end -> begin left right end left right -> left left right right left right -> a b 1 2 c 3

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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