Tutorial Week 4 (Solutions)
Task 1.This one is very simple.
• 16 * 17 *
• / \ = 272
• 16 17
•
• 2 + 3 + 4 + +
• / \ / \
• + 4 = 9 , 2 + = 9
• / \ / \
• 2 3 3 4
•
• 2 * 3 + 4 * 5 *
• / \
• 2 +
• / \ = 46
• 3 *
• / \
• 4 5
•
•
• *
• / \
• 2 +
• / \ = 34
• * 5
• / \
• 3 4
•
•
• +
• / \
• * * = 120
• / \ / \
• 2 3 4 5
•
•
• *
• / \
• + 5
• / \
• * 4 = 50
• / \
• 2 3
•
•
• +
• / \
• * 5
• / \
• 2 + = 19
• / \
• 3 4
•
Task 2.
• ((01*0) | (1(00)*1))? S → ε | A | B
• A → 0A’0
• A’ → 1A’ | ε
• B → 1B’1
• B’ → 00B’ | ε
•
• ((01*0) | (1(00)*1))+ S → A | AS
• A → B | C
• B → 0B’0 | ε
• B’ → 1B’ | ε
• C → 1C’1
• C’ → 00C’ | ε
•
• Palindromes over {0, 1} are generated by: S → ε | 0S0 | 1S1 | 0 | 1
•
• The language given by the regular expression 0*1* with the additional constraint that there must be more 0s than 1s. S → STS
• T → ε | 0T | T0 | 1T0T | T0T1
•
Here is an alternative grammar doing the same thing. S → STS
• T → ε | 0T | T0 | T01T | T01T
•