3. An elementary school teacher needs to generate mathematical problems to pupils. This week's problem is...

Transcribed Image Text:

3. An elementary school teacher needs to generate mathematical problems to pupils. This week's problem is about counting if the first two baskets have in total the same number of apples than the third basket. Let Σ = {a, +, =}, where “a” stands for the apple, “+” is the addition, and “=” refers to the "equals to". The task is to generate strings of form: a. a+a ...a = a. ...a i apples j apples k apples where i, j, k ≥ 0 and i + j> k, i.e. false statements with too few apples on the right-hand side. Let A denote the corresponding language, where both + and = must exist. So the two shortest strings in A are a+ = and +a =, corresponding to having one apple in one of the first two baskets and no apples on the third basket. Show that A is context-free. bd 3. An elementary school teacher needs to generate mathematical problems to pupils. This week's problem is about counting if the first two baskets have in total the same number of apples than the third basket. Let Σ = {a, +, =}, where “a” stands for the apple, “+” is the addition, and “=” refers to the "equals to". The task is to generate strings of form: a. a+a ...a = a. ...a i apples j apples k apples where i, j, k ≥ 0 and i + j> k, i.e. false statements with too few apples on the right-hand side. Let A denote the corresponding language, where both + and = must exist. So the two shortest strings in A are a+ = and +a =, corresponding to having one apple in one of the first two baskets and no apples on the third basket. Show that A is context-free. bd

Answer rating: 100% (QA)

To show that language A is contextfree we can construct a contextfree grammar CFG that generates all ... View the full answer