Programming languages are often described using an extended form of context-free

Question

Programming languages are often described using an extended form of context-free grammar, where curly brackets are used to denote a construct that can repeat 0, 1, 2, or any number of times. For example, A B{C}D says that an A can be replaced by a B and a D, with any number of C's (including 0) between them. This notation does not allow us to describe anything but context-free languages, since an extended production can always be replaced by several conventional productions.

Suppose a grammar has the extended production:

A 0{1}2

Convert this extended production to conventional productions. Identify, from the list below, the conventional productions that are equivalent to the extended production above.

a) A 0A112 A1 A11 |

b) A 0A12 A1 1A1 | 1

c) A 0A12 A1 A11 | 1

d) A 0A12 A1 A11 |

please answer my question

very confused how to do

Explanation / Answer

d) A 0A12; A1 A11 | ; is the right answer.

Hint :-

A 0{1}2 says that an A can be replaced by a 0 and a 2, with any number of 1's (including 0) between them.

option (a), (b) and (c) do not have zero number of 1. it always more then zero.

So option d is correct.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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